CS 181 FINAL EXAM NAME FALL 2019 UCLA ID
You have 3 hours to complete this exam. You may state without proof any fact taught in class or assigned as homework. Your algorithms must terminate on all inputs.
(3 pts) (3 pts)
1
Construct one-tape, deterministic Turing machines for the tasks below. You must provide both a state-transition diagram and a detailed verbal description:
a. a Turing machine that decides the language {0n10n : n 0};
b. a Turing machine that computes the function sort: {0,1}∗ → {0,1}∗, which rear-
ranges the bits of the input string in sorted order. For example, sort(1010) = 0011.
Solution.
a. The TM shuttles back and forth on the input, alternately erasing a 0 from the left end and a 0 from the right end. At all times, the blank cells serve to delimit the remaining part of the string. When the string shrinks to “1,” the TM accepts it. The state-transition diagram is as follows.
0, 1 → R 0, 1 → L
qaccept ⊔ 1→R q0 0→⊔,R ⊔→L 0→⊔,L ⊔→R
b. The TM starts by scanning the input string looking for a 1. If the string contains only 0s, then it is already sorted, and the TM halts. Otherwise, the TM overwrites the first 1 with an x to mark it as a candidate for a swap, and scans from then on for a 0. If it finds no 0s, then the string is sorted, so the TM returns to the x, changes itbacktoa1,andhalts. IftheTMdoesfinda0,thenitchangesittoa1,returns to the x, changes it to a 0, and recursively sorts the remainder of the string from that point on. The state-transition diagram is below.
qhalt
1→L x → 0, R
0 → 1, L
1→L 1→R
0→R
q0
⊔→L
(3 pts)
2 Give an algorithm that takes as input a PDA P and a symbol γ of its stack alphabet, and decides whether P ever pops γ from the stack in any computation.
Solution. Let P = (Q, Σ, Γ, δ, q0, F ) be given. Construct a PDA P ′ that operates just like P but accepts if and only if γ has been popped from the stack at some point. This can be achieved by “remembering” in state whether γ has been popped. Formally, P′ =({yes,no}×Q,Σ,Γ,∆,(no,q0),{yes}×Q),where
∆((b,q),σ,τ) =
{yes}×δ(q,σ,τ) ifτ=γ, {b} × δ(q, σ, τ ) otherwise,
for all b ∈ {yes,no}, σ ∈ Σ∪{ε}, and τ ∈ Γ∪{ε}. Now that P′ has been constructed, convert it to a context-free grammar and check whether its language is nonempty.
⊔
1 → x, R
x→1
(0.5 pts) (2.5 pts)
3
For a nonempty language L, the longest common prefix of L is denoted lcp(L) and defined as the longest string w such that all strings in L start with w. For example, lcp({0111, 0101}) = 01 and lcp(0+ ∪ 1+) = ε.
a. For every nonempty language L, prove that lcp(L) exists and is unique.
b. Give an algorithm that inputs a PDA P with L(P ) ̸= ∅ and computes lcp(L(P )).
Solution.
a. If u and v are common prefixes of L, then one of them is a prefix of the other. Therefore, the only way they can both be longest prefixes of L is if u = v. This proves the uniqueness of lcp(L). To prove existence, consider the set A of common prefixes of L. Then A is nonempty (because ε ∈ A) and finite (because the strings in A are bounded in length by the shortest string in L). Thus, A has a longest string.
b. We compute lcp(L(P)) iteratively, building it up one character at a time starting with the empty prefix. Formally, initialize p ← ε. In each iteration, we look for σ ∈ Σ such that L(P) ⊆ pσΣ∗. If found, we set p ← pσ and start the next iteration; if not, we know that p is maximal and hence lcp(L(P )) = p.
The basic operation in this algorithm is testing whether L(G) ⊆ vΣ∗, for a nonempty string v = v1v2 . . . vn. To implement this test, start by constructing an NFA for vΣ∗:
v1 v2 v3 vn−1 ̸= v ̸= v2 ̸= v3 ̸= v
Σ
Then apply the Cartesian product construction to P and N to obtain a PDA P ′ for L(P ) ∩ vΣ∗. Finally, convert P ′ to a context-free grammar and check whether its language is empty.
1n
(3 pts) (2 pts)
4
For a language L, a motif of L is any string that occurs as a substring in infinitely many strings of L. Prove that the following problems are decidable:
a. on input a DFA D and a string w, decide whether w is a motif of L(D);
b. on input a DFA D, compute the number of motifs of L(D) (an integer or “∞”).
Solution.
a. Let w = w1w2 …wn be given. By definition, w is a motif iff L(D) ∩ (Σ∗wΣ∗) is infinite. With this in mind, construct an NFA N for Σ∗wΣ∗:
ΣΣ
w1 w2 w3 wn
Next, convert this NFA to a DFA and combine the result with D via the Carte- sian product construction to produce a DFA for L(D) ∩ (Σ∗wΣ∗). Finally, use the algorithm from class to check whether this new DFA accepts infinitely many strings.
b. If L(D) is finite, then by definition L has no motifs. If L(D) is infinite, then the pumping lemma ensures that xy∗z ⊆ L for some nonempty string y, which means that L has infinitely many motifs (y, y2, y3, . . .). This motivates the following solution: use the technique from class to check whether L(D) is infinite, and output “∞” in that case and 0 otherwise.
(2 pts) (3 pts)
(3 pts)
5
For each problem below, determine whether it is decidable and prove your answer:
a. on input a Turing machine M , decide whether L(M ) is regular;
b. on input a Turing machine M that recognizes a regular language, compute a regular expression for L(M);
c. on input a Turing machine M, decide whether M accepts every input in at most 2019 steps.
Solution.
a. Undecidable. Let C be the set of regular languages. Then C is a nonempty proper subset of Turing-recognizable languages because, for example, C contains 0∗ and does not contain {0n1n : n 0}. Rice’s theorem now implies that it is undecidable, on input a Turing machine M, whether L(M) ∈ C.
b. Undecidable. For the sake of contradiction, suppose that this problem can be solved by some Turing machine T . Then the following algorithm is a decider for the halting problem.
Input: Turing machine M, string w
1:
2: 3: 4: 5: 6:
newTM ←
if T (newTM) = Σ∗ then return “M halts on w”
else
return “M does not halt on w”
end if
Input: x RunM onw Accept x
On input M,w, the above algorithm constructs a Turing machine called newTM such that L(newTM) = Σ∗ if M halts on w, and L(newTM) = ∅ otherwise. Thus, the language of newTM is regular and reveals whether M halts on w. Next, the algorithm runs T on newTM and checks whether the resulting regular expression is equivalent to Σ∗, using the equivalence test for regular expressions from class. Altogether this gives a decider for the halting problem. Since the halting problem is undecidable, we conclude that T cannot exist in the first place.
c. Decidable. A Turing machine that runs for at most 2019 steps cannot go beyond the first 2019 symbols of the input. This motivates the following algorithm. Run M on every string of length at most 2019, cutting off each such execution at 2019 steps. If all these executions result in acceptance, output “yes.” Otherwise, output “no.”