- Review: Textbook, Problem 1.16 (a) and (b), page 86.
- 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.

Topic revision: r1 - 2012-03-12 - 01:59:09 - 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 |