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).
    Note: You may omit the dead state and the transitions that lead to the dead state.
  2. Let M be a 3-Tape Turing machine with input alphabet {0, 1, 2}, and tape alphabet {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 closed under:
    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 every L_i must be decidable.
  7. Deferred until next problem set: 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

Topic attachments
I Attachment Action Size Date Who Comment
PDFpdf ThreeStateNFAHomework8_1b.pdf manage 16.6 K 2012-03-12 - 15:24 UnknownUser  
PDFpdf TwoStateNFAHomework8_1a.pdf manage 10.0 K 2012-03-12 - 15:24 UnknownUser  
Topic revision: r5 - 2012-03-15 - 19:02:52 - Main.ctanti2
Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF