TWiki> CS301 Web>Syllabus>Homeworks>ProblemSet9 (2012-03-24, Main.sloan)

## 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 WISESTHelping Women Faculty AdvanceFunded by NSF