CS 332: Theory of Computation Professor Mark Bun Boston University March 12, 2020
Homework 4 – Due Wednesday, March 18, 2020 before 2:00PM
Reminder Collaboration is permitted, but you must write the solutions by yourself without assistance, and be ready to explain them orally to the course staff if asked. You must also identify your collaborators. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Exercises Please practice on exercises and solved problems in Chapter 3. The material they cover may appear on exams.
Problems There are 3 mandatory problems and one bonus problem. 1. (TM descriptions)
(a) Give the sequence of configurations that the following TM M enters when given as input strings 1##1 and 0#0. Please use the same representation for your configurations as we did in lecture 10.
The reject state and transitions to the reject state are not shown. Whenever the TM encounters a character for which there is no explicit transition that means that the TM goes to the reject state. We say that the head moves right in each of these transitions to the reject state.
start q1
# → R 1 → x, R 0 → x, R
0, 1 → R q2 x → R q8 0, 1 → R q3
x→R #→R →R #→R
x→R q4
0, 1 → L q7
qaccept x→R q5 0 → x, L
#→L 1
1 → x, L q6 0, 1, x → L
(b) Give an implementation level description of a TM, possibly nondeterministic and/or with multiple tapes, that recognizes the following language over the alphabet {0,1}: {s#a1#a2# . . . #an | where n is a positive integer,
s,a1,…,an are binary integers such that some subset of a1,…,an sums to s}.
(c) Give a state diagram of the TM whose implementation level description is below.
“On input w
1. If the first symbol is blank then accept. If it is b then reject. If it is a then
erase this a and go to the right and go to the next step.
2. Move the head on the tape right until the blank symbol is found. After it is found move the head to the left (to the last symbol of the string) and
go to the next step.
3. If the last symbol is not b then reject. Otherwise, erase this b and go to
the left and go to the next step.
4. Move the head on the tape left until the blank symbol is found. After it
is found move the head to the right (to the first symbol of the string) and go back to step 1.”
(d) What language is decided by the TM from (c)?
2. (Closure properties) Show that the class of decidable languages is closed under
(a) complement (b) concatenation
Show that the class of Turing-recognizable languages is closed under
(c) star
(d) Explain why your construction from 2(a) fails to show that the Turing-recognizable languages are closed under complement.
3. (Multi-stack PDA) Consider a PDA with multiple stacks.
(a) Give an example of a language that a 2-stack PDA can recognize, but no usual PDA can recognize. Give an implementation-level description of the 2-stack PDA that recognizes your language.
(b) Show that a 2-stack PDA can simulate a Turing machine.
(c) Is there a language that a 3-stack PDA can recognize, but no 2-stack PDA can recognize?
Explain.
4∗ (Bonus, no collaboration is allowed)
(a) Show that a language is decidable iff some enumerator enumerates the language in the standard string order.
(b) Show that every infinite Turing-recognizable language has an infinite decidable subset.
Hint: use part (a)
2