(r3) ProblemSet8 < CS301

CS301 Web>Syllabus>Homeworks>ProblemSet8 (revision 3) (raw view)~~EditAttach~~

---++ Problem Set 8, CS 301 Spring 2012
---+++ Due Friday, March 16 (right before the start of Spring Break)
   1 Review: We need more practice converting NFAs to DFAs. We already did textbook, Problem 1.16 (a) and (b), page 86, in a much earlier homework. Now please convert, by hand, the two DFAs given in the attached files in the attachment table at the bottom of this web page. You should generate the DFA states "as needed". For these two particular problems, your solution DFA should have strictly less than 2 to the power of the number of states of the NFA (which is the general worst case for this construction).
   1 Let M be a 3-Tape Turing machine with input alphabet {0, 1, 2}, and tape alphabe {0, 1, 2, 3, 4, blank}. Using either the construction from lecture or the textbook page 149 (which are similar in spirit but different in details), how big will the tape alphabet have to be for an equivalent single-tape Turing machine S? Tell which simulation you are using (class or textbook), and briefly justify your answer.
   1 Give a rigorous argument that the set of regular languages is a _strict_ subset of the decideable languages.
   1 Show that the set of decidable languages is closed under: 
      1 Concatenation
      1 Kleene Star
      1 Reverse
   1 Show that the set of Turing-recognizable languages is closed under: 
      1 Concatenation
      1 Kleene Star
      1 Reverse
   1 Fix an alphabet <latex> \Sigma </latex> and a posive integer n. Imagine that you are given a collection of n languages <latex> L_1, L_2, \ldots, L_n </latex> such that: 
      * Each <latex> L_i</latex> is Turing recognizable,
      * The union of all n of the <latex> L_i</latex>; is <latex> \Sigma^*</latex>
      * No two distinct <latex> L_i, L_j </latex> have any strings in common. Prove that every <latex> L_i </latex> must be decidable.
   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.
-- Main.sloan - 2012-03-12

   * [[%ATTACHURL%/ThreeStateNFAHomework8_1b.pdf][ThreeStateNFAHomework8_1b.pdf]]: ThreeStateNFAHomework8_1b.pdf