CS 332: Elements of Theory of Computation Prof. Mark Bun
Boston University March 18, 2021
Test 2
� Read all the instructions on this page before beginning the exam.
� Your solutions must be scanned and uploaded to Gradescope by 11:59PM Eastern Daylight Time,
Friday, March 26, 2020.
� We are flexible with the format in which you complete the exam and upload the solutions. Blank
space is provided if you wish to print the exam out and write your solutions on it, or if you wish
to download the PDF and fill it out on a tablet. You may also prepare your solutions on your
own paper as if you were completing a homework assignment. Both handwritten and typeset
solutions are allowed. Make sure to clearly indicate which problem you are solving, both on your
written solution and when you submit to Gradescope.
� This exam contains 5 problems, some with multiple parts. The test is worth 100 points.
� The exam is open-book in that you may freely consult the Sipser textbook, lecture notes and
videos posted online, past homework assignments and solutions, discussion worksheets, your own
class notes, and discussions on Piazza. You may not use any outside resources beyond those
listed here.
� You must complete the exam by yourself. No collaboration with anyone is permitted.
� You do not need to spend time and paper rederiving facts that we have studied. You may
cite known results and examples which were stated in lecture or proved in the main
body of the text. This does not include homework problems, discussion section problems, or
the solved exercises/problems in the text. You are, of course, free to use such results but you
have to prove them first.
� You will be graded not only on the correctness of your answer, but also on the clarity with which
you express it. Make your writing large and neat.
� If you need to ask a clarification question about one of the problems, please do so in an instructor-
only post on Piazza. If the course staff believes your question may be a common one, we will
change the settings of your post to be public to the class, keeping your identity anonymous.
� Good luck! We hope you have fun solving these problems.
1
Problem 1 (True or False, 20 points). Indicate whether each of the following statements is true or
false. Justify your answer in two or three sentences. False statements should be justified by a specific
counterexample. No points will be given even for a correct answer if no justification is
presented.
(a) A Turing machine with two tapes can recognize more languages than a TM with a single tape
that extends infinitely in both directions.
(b) ALLTM = ETM. Here, ALLTM = {〈M〉 |M is a TM that recognizes Σ∗} and ETM = {〈M〉 |
M is a TM that recognizes the empty language}.
(c) There exists a nondeterministic Turing machine that recognizes the language A = {〈M,w〉 |
M is a TM and M accepts input w}.
(d) One can write a Python program that takes as input the code P for another Python program
and a string w and decides whether P halts on input w. (That is, the program halts and
accepts when P halts on input w, and halts and rejects when P loops on input w.)
(e) The complement of a regular language is always Turing-recognizable.
Problem 2 (TM with Pointer, 16 points). A pointer TM is the same as a two-tape TM, except
instead of moving the heads left or right at the end of a computational step it may instead “follow
the pointer” resulting in the following action: Let w be the string appearing on tape 2 from the
first cell (inclusive) through the first blank cell (exclusive). Move the head on tape 1 to cell |w|.
The head on tape 2 does not move.
Example: If the contents of tape 1 are the string 0000100 and the contents of tape 2 are the
string 10101t010, then a “follow the pointer” instruction would result in the head of tape 1 moving
to the 5th cell (the cell on tape 1 containing a ‘1’), and the head of tape 2 staying wherever it was.
(a) Explain, in one sentence, why every Turing-recognizable language is also recognizable by a
pointer TM. (4 points)
(b) Give a simulation argument, using an implementation-level description, to show that every
language recognizable by a pointer TM is also Turing-recognizable. (12 points)
Problem 3 (Countable and Uncountable Sets, 24 points). new line
(a) Show that the set R of all regular expressions over the alphabet {a, b} is countable. (12
points)
(b) A language L ⊆ {0, 1}∗ is sparse if for every length n = 0, 1, 2, . . . , the language L contains
at most one string of length n. For example, {0n1n | n ≥ 0} is sparse because it contains one
string of every even length and zero strings of every odd length. But {0m1n | m,n ≥ 0} is
not sparse because, e.g., 00 and 01 are both strings of length 2 that are in this language.
Use a proof by diagonalization to show that S = {L ⊆ {0, 1}∗ | L is sparse} is uncountable.
(12 points)
Hint: Index the rows of your diagonalization matrix by sparse languages L1, L2, L3 . . . and
the columns by strings 1, 11, 111, . . . Let cell (i, j) contain the answer to the question “Is
string 1j in language Li?”
2
Problem 4 (Self Acceptance, 28 points). Hint: You can save a lot of time and energy understanding
each of these languages by relating them to languages we already studied in class. Remember that
you don’t need to start from scratch if you can use a recognizer or decider for a problem we’ve
already studied as part of your solution.
(a) Give a high-level description of a Turing machine that decides the language
SNFA = {〈N〉 | N is an NFA that accepts the string 〈N〉} and briefly explain why your de-
cider is correct. (10 points)
(b) Give a high-level description of a Turing machine that recognizes the language
STM = {〈M〉 | M is a TM that accepts the string 〈M〉} and briefly explain why your recog-
nizer is correct. (8 points)
(c) Is STM decidable? Explain your answer. (4 points)
(d) Is STM Turing-recognizable? Explain your answer. (4 points)
Problem 5 (TM vs. Regular Expression, 14 points). Consider the following computational prob-
lem. Given a Turing machine M and a regular expression R, is the language recognized by M equal
to the language generated by R?
(a) Formulate this problem as a language EQTM,REX. (4 points)
(b) Show that EQTM,REX is undecidable by giving a reduction from the undecidable language
ETM. Make sure to explain why the TM computing your reduction is correct. (10 points)
3