(3 pts)
CS 181 FINAL EXAM NAME ________________________________ FALL 2016 UCLA ID ________________________________
You have 3 hours to complete this exam. You may state without proof any fact taught in class or assigned as homework.
1 Let L be the language of binary strings whose length is a perfect square (0; 1; 4; 9; 16; 25; 36; : : :). Give a detailed verbal description of a multi-tape Turing machine that decides L.
Solution. The idea is to consider every integer n D 0;1;2;3;:::, in each case computing n2 and comparing the result to jwj: We can stop as soon as n2 > jwj: In more detail, the algo- rithm is as follows.
Input: string w 2 f0; 1g⇤
for n D 0;1;2;3;::: do N n2
if jwj < N then
output “jwj is not a perfect square”
else if jwj D N then
output “jwj is a perfect square” end
We will implement this algorithm using a Turing machine with three tapes: the input tape with the string w written on it, and two additional tapes. At the start of an iteration, the second tape contains 0n for the current value of n; and the third tape is blank. The Turing machine marks the first cell of 0n with a dot and then copies 0n to the third tape symbol by symbol (using an additional moving mark to implement the copying). The Turing machine then advances the dot to the next symbol of 0n on the second tape and again copies 0n to the third tape, appending it to the third tape’s current contents. The process continues until the dot moves beyond the last sym- bol of 0n on the second tape. At that point, the third tape contains 0n2 ; which can be compared symbol by symbol with w to find out which one is longer. The computation halts immediately if jwj D n2 or jwj < n2; with the Turing machine entering qaccept and qreject; respectively. If jwj > n2; the Turing machine increments n (by appending a 0 to the second tape), erases the third tape, and starts a new iteration.
(4 pts)
2 Draw the transition diagram for a Turing machine that decides the language of palindromes over the binary alphabet.
Solution.
qaccept
0; 1 ! R t ! R 0; 1 ! R 1 ! t; R q0 0 ! t; R
t!L t!R t!L
1;t ! t;L
0;t ! t;L
(3 pts)
3 Let A be the language whose strings are binary encodings (with leading zeroes ignored) of multiples of 2016. Thus, A contains “; 0; 00; 11111100000; 0011111100000 but not 1; 10; 11: Describe an algorithm that takes as input a context-free grammar G and determines whether G generates some string in A:
Solution. We first build a DFA for A. The DFA works by converting the input on the fly to a dec- imal number and checking if that number is divisible by 2016: A literal implementation of this idea produces the infinite “automaton” .f0;1;2;:::g;f0;1g;ı;0;f0;2016;4032;6048;:::g/; where ı.q; / D 2q C : To get an actual DFA for A; recall that we only care about the re- mainder of the decimal number modulo 2016: Therefore, we can perform all intermediate com- putations modulo 2016: This gives the DFA .f0; 1; 2; : : : ; 2015g; f0; 1g; ı; 0; f0g/ for A; where ı.q; / D .2q C / mod 2016:
To check if a given context-free grammar G generates a string in A; we start by converting G to a PDA. We then combine this PDA with the DFA for A via the Cartesian-product con- struction, obtaining a PDA for L.G/ Z A. Finally, we check whether this PDA for L.G/ Z A accepts any strings, by converting it to a grammar and checking whether the grammar generates any strings. For each of these steps, we gave an algorithm in class.
0; 1 ! L
(3 pts) (3 pts)
4
Prove that the following problems concerning finite automata with alphabet f0; 1g are decidable:
a. on input a DFA D, determine whether D accepts infinitely many palindromes;
b. on input a DFA D; determine whether D accepts a pair of distinct strings u and v such that u is a prefix of v.
Solution.
a. Rephrasing, we need to determine whether L.D/ Z P is infinite, where P is the context- free language of palindromes. Construct a PDA for L.D/ Z P by applying the Cartesian- product construction to a PDA for P and the given DFA D. Then, convert the resulting PDA to a grammar and use the algorithm from class to check whether the grammar accepts infinitely many strings.
b. Use any graph search algorithm to identify the set F 0 of accept states of D that are reach- able from the start state. Output “yes” if and only if there exists a pair of states q0; q00 2 F (not necessarily distinct) with a path of nonzero length from q0 to q00:
(3 pts) (3 pts) (3 pts)
5
For each of the problems below, determine whether it is decidable, and prove your answers:
a. on input a Turing machine M; determine whether there is a DFA with at most 2016 states
that recognizes the same language as M ;
b. on input a Turing machine M and a string w; determine whether M ever moves left while
computing on w;
c. on input a Turing machine M; determine if there is an integer c (perhaps very, very large)
such that M terminates within c steps on every input.
Solution.
a. Undecidable. We showed in class that some languages such as 0⇤1⇤ have a DFA with at most 2016 states, whereas others such as f0n1n W n > 0g have no DFA at all, let alone a DFA with at most 2016 states. Thus, the language property of having a DFA with at most 2016 states is nontrivial. Rice’s theorem now implies that it is undecidable whether a given Turing machine recognizes a language with this property.
b. Decidable.JustrunM onwforjwjCjQjC1steps,whereQisthesetofstatesofM:If M has moved left at any point, output “yes”; otherwise, output “no.” To see why we can cut the simulation off after this many steps, suppose that M goes on for jwjCjQjC1 steps without ever moving left. Then M moves through every symbol of w and then through an additional jQj C 1 blank cells. As M moves through the jQj C 1 blanks, it goes through jQj C 1 states, which by the pigeonhole principle cannot all be distinct. Once M repeats a state in its onward march through the blanks, it gets stuck in a cycle and is forced to keep moving right forever.
c. Undecidable. For the sake of contradiction, assume that this problem can be solved by some Turing machine, which we will call STOPWATCH. Then the following algorithm solves the (undecidable!) halting problem:
Input: Turing machine T; string x
if STOPWATCH⇥ ⇤ D “yes” then
output “T halts on x” elseoutput “T does not halt on x”
Input: stringw
Run T on x (ignoring w)
For any input T; x; the above algorithm constructs a Turing machine (on the fly, specially tailored to T and x) whose running time is bounded on all inputs by a constant c if and only if T halts on x. Then, the algorithm runs STOPWATCH on the newly constructed machine to find out the answer.