CS 301, Spring 2012 Problem Set 9

  1. Let L be a language that has an enumerator that outputs all the strings of L in lexicographic order. (Review Sipser, page 14 if you have forgotten lexicographic order.) Show that L must be decidable.
  2. Let L_1 \subset L_2 \subset L_3 be three distinct languages such that both L_1 and L_3 are decidable. What can we say about L_2 ? Does it have to be decidable, or at least Turing-recognizable? If yes, why? If no, give a particular example with three languages.
  3. If L_1, L_2 are both decidable, then Is it always true that L_1 \setminus L_2 is decidable? (Remember \setminus is set difference.) If yes, why; if no; please give cournterexample.
  4. If L_1, L_2 are both undecidable, then is it possible that: (For each part give an example if it's possible, and an argument why if it's impossible.)
    1. L_1 \cup L_2 is decidable?
    2. L_1 \setminus L_2 is decidable?
-- Main.sloan - 2012-03-24
Topic revision: r2 - 2012-03-24 - 13:36:20 - Main.sloan
Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF