Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 162--Formal Languages and Automata Theory
1. (50 points). General Concepts.
(a) How is a nondeterministic Turing machine’s transition function different than that for a deterministic Turing machine?
(b) What is the Church-Turing thesis?
2. (50 points). Undecidability.
(a) Draw a Venn diagram that illustrates the relationships between the following classes of languages: regular languages, context-free languages, decidable languages, Turing-recognizable languages.
(b) Give an example of a language that is undecidable. (You don’t need to prove that it is undecidable, however.)
3. (50 points). Countability. Show that the set, {3, 6, 9, 12, 15, . . .}, of positive multiples of 3 is countable.
4. (50 points). Context-free Languages. Use the pumping lemma for context-free languages to show that the language L = {1
n2
n3
n
| n ≥ 1} is not context free.
5. (50 points). Turing Machines. Show that the language L = {1
n2
n3
n
| n ≥ 1} is decidable by giving a high-level of a description of a Turing Machine that accepts strings in L and rejects strings not in L.
6. (50 points). Universal Turing Machines. Consider the language, FTM = {(M, w, n) | M is a Turing Machine and M accepts the string w in at most n steps}.
Is FTM decidable? Why or why not? (Prove your answer.)