TWiki> CS301 Web>Syllabus>Homeworks>ProblemSet9 (revision 1)EditAttach

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 <latex> L_1 \subset L_2 \subset L_3 </latex> be three distinct languages such that both <latex> L_1 </latex> and <latex> L_3 </latex> are decidable. What can we say about <latex> L_2 </latex>? 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 <latex>L_1 </latex> and <latex> L_2 </latex> are both decidable, then
    1. Is it always true that
    2. More coming; problem set writing in progress.
-- Main.sloan - 2012-03-24
Edit | Attach | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r1 - 2012-03-24 - 03:06:51 - Main.sloan
Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF