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

Problem Set 8, CS 301 Spring 2012

Due Friday, March 16 (right before the start of Spring Break)

  1. Review: Textbook, Problem 1.16 (a) and (b), page 86.
  2. 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.
  3. Give a rigorous argument that the set of regular languages is a strict subset of the decideable languages.
  4. Show that the set of decidable languages is closed under:
    1. Concatenation
    2. Kleene Star
    3. Reverse
  5. Show that the set of Turing-recognizable languages is closued uner:
    1. Concatenation
    2. Kleene Star
    3. Reverse
  6. Fix an alphabet \Sigma and a posive integer n. Imagine that you are given a collection of n languages L_1, L_2, \ldots, L_n such that:
    • Each L_i is Turing recognizable,
    • The union of all n of the L_i; is \Sigma^*
    • No two distinct L_i, L_j have any strings in common. Prove that ever L_i must be decidable.
  7. 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
Edit | Attach | Print version | History: r5 | r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r1 - 2012-03-12 - 01:59:09 - Main.sloan
Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF