COMS 331: Theory of Computing, Spring 2021 Final Exam
10:00AM-10:00PM, Wednesday, May 5, on Gradesccope.
You have FOUR hours to complete and submit this exam. There are twelve problems, worth 400 points in total (70 points for question 1 and 30 points for each of the others). Any problem that you leave blank or indicate clearly that you do not want graded will receive 30% credit. Every other problem will be graded and receive 0-10 points for each part of question 1, and 0-30 points for the other questions. All answers should be explained, at least briefly.
For problem 2 and 3, providing a state diagram or transition table will suffice.
While taking the exam you MAY
• consult your own notes and the lecture notes;
• consult the textbook and the class lectures;
• contact the instructor or TA with questions about the exam. (We’ll try to answer promptly, but cannot guarantee that.)
While taking the exam you may NOT
• post questions or any information about the exam;
• discuss the exam with anyone except the instructor and TAs;
• work with anyone else or access any other resources or websites.
If you want the tex file of this exam, please go to
https://iastate.box.com/s/h3q9ykt1v18veg6nsswm42sx46dt0u1p
1
Problem 1. (70 points) For each of the following, either give an example of a language with the indicated property, or state that no such language exists. (For this problem, you do not need to prove that your answers are correct.)
(a) A regular language whose complement is not regular.
(b) A decidable language whose complement is not regular.
(c) A language that is neither c.e. nor co-c.e.
(d) A regular language that is ≤m-complete for the class CE of all c.e. languages. (e) An infinite language A ⊆ {0, 1}∗ such that C (x) ≤ 21000 for all x ∈ A.
(f) A finite language that is c.e.
(g) A c.e. language that is not co-c.e.
Problem 2. (30 points) Design a DFA that decides the language
A = {x ∈ {0, 1}∗ | x contains 2 consecutive 0s and does not contain 2 consecutive 1s}.
Problem 3. (30 points) Design a Turing machine that, on input x ∈ {0, 1}∗, eventually halts with the string
0#(0,x) 1#(1,x)
on its tape. (Note: #(0, x) is the number of 0s in x, and #(1, x) is the number of 1s in x.)
Problem 4. (30 points) Prove that the language
A = {0|x|1xy|x,y ∈ {0,1}∗}
is not regular.
NOTE: A proof using the pumping lemma will receive full credit if correct, but is not eligible for partial credit. The ordinal extension nonregularity method is recommended here.
2
Problem 5. (30 points) The symmetric difference between languages A, B ⊆ {0, 1}∗ is A△B = (A − B) ∪ (B − A).
(The notation A ⊕ B is also often used for A△B.)
Prove: If A is regular and A△B is finite, then B is regular.
Problem 6. (30 points) Let A ⊆ {0, 1}∗ and f : {0, 1}∗ −→ {0, 1}∗. Prove: If A is decidable and f is computable, then the image
f(A) = {f(x)|x ∈ A}
is c.e.
Problem 7. (30 points) Given languages A, B ⊆ {0, 1}∗, let
A ⊗ B = {⟨x, y⟩ | x ∈ A and y ∈ B},
where ⟨x, y⟩ = 0|x|1xy. Prove: If A is ≤m-hard for CE and B is ≤m-hard for coCE, then A ⊗ B is ≤m-hard for CE ∪ coCE.
Problem 8. (30 points) Let M0,M1,M2,… be the standard enumeration of all Turing machines that have input alphabet {0, 1}. Prove that the set
A = {n ∈ N | Mn accepts all strings of even length}
is undecidable.
Problem 9. (30 points) Let A = {x ∈ {0,1}∗ |#(1,x) = 3}, where #(1,x) is the number of 1s in x. Prove that there is a constant c ∈ N such that, for all x ∈ A,
C(x) ≤ 8 log(1 + |x|) + c
NOTE: It is possible to do this with a coefficient smaller than 8, but that is not required for full credit.
3
Problem 10. (30 points) Let U be the fixed optimal Turing machine that we used to define Kolmogorov complexity. Prove that there is a constant c ∈ N such that, for all π, x ∈ {0, 1}∗, if
U(π) = x and |π| = C(x),
then
C(π) ≥ |π| − c.
(That is, if π is a shortest program for x, then π cannot be compressed very much.)
Problem 11. (30 points) Construct the equivalent DFA to the following NFA using subset con- struction. Remove all unreachable states for your final answer.
1
s0t0u
1
Problem 12. (30 points) Write the regular expression (over the alphabet {a, b}) for strings whose length is a multiple of 3, and every 3n-th character (where n ∈ Z+) is different from the previous two. (For example, you should match aab and bbaaab, but not a, aba, or aababb.)
4
0
v