- 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).
- 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.
- Give a rigorous argument that the set of regular languages is a
*strict*subset of the decideable languages. - Show that the set of decidable languages is closed under:
- Concatenation
- Kleene Star
- Reverse

- Show that the set of Turing-recognizable languages is closued uner:
- Concatenation
- Kleene Star
- Reverse

- Fix an alphabet
\Sigma and a posive integer n. Imagine that you are given a collection of n languagesL_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 everL_i must be decidable.

- Each
- 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.

I | Attachment | Action | Size | Date | Who | Comment |
---|---|---|---|---|---|---|

ThreeStateNFAHomework8_1b.pdf | manage | 16.6 K | 2012-03-12 - 15:24 | UnknownUser | ||

TwoStateNFAHomework8_1a.pdf | manage | 10.0 K | 2012-03-12 - 15:24 | UnknownUser |

Topic revision: r2 - 2012-03-12 - 15:26:28 - Main.sloan

Copyright 2016 The Board of Trustees of the University of Illinois.webmaster@cs.uic.edu |
WISEST Helping Women Faculty Advance Funded by NSF |