COM S 331: Theory of Computing, Summer 2021
Final Exam
Designated exam time 11:00 am – 2:00 pm(3 hours), Friday, July 9, on Gradescope.
You have 3 hours to complete and submit this exam. There are six problems, worth 200 points
in total. Any problem that you leave blank or indicate clearly that you do not want graded will
receive 20% credit. Every other problem will be graded and receive 0-30 points for problem 1
to 4, 0-40 for problem 5 and 6. All answers should be explained, at least briefly.
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 (etc on chegg);
• discuss the exam with anyone except the instructor and TA;
• work with anyone else or access any other resources or websites.
1
You can use high-level descriptions for describing Turing machines.
Problem 1 (30 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. The 20% policy applies to individual sub-problems.)
(a) A regular language which is not context-free.
(b) A decidable language whose complement is not regular.
(c) A context-free language that is regular.
(d) A regular language L that reduces to ATM = {〈M,w〉 | M is a TM, and M accepts w}, i.e.
L ≤m ATM .
(e) A finite language that is Turing decidable.
(f) A Turing-recognizable language that is not co-Turing-recognizable.
Problem 2 (30 points). Prove or Disprove: A and B are languages over the alphabet Σ. If A ⊆ B
and B is regular, then A is regular.
Problem 3 (30 points). Prove that the set of Turing-decidable languages is closed under reversal,
i.e., if L is Turing-decidable, then LR = {x ∈ Σ∗ | xR ∈ L, where xR is the reverse of x} is Turing
decidable.
(To help you understand the relationship between L and LR.
Example: If L = {abc, c, aabb}, then LR = {cba, c, bbaa})
Problem 4 (30 points). Let f : N −→ N be a Turing-computable function.
Prove: If f(n) < f(n + 1) for all n ∈ N, then L = {f(n) |n ∈ N} is decidable.
(To help you understand L, L can be written as L = {x ∈ N | ∃n ∈ N such that x = f(n)}).
Problem 5 (40 points). Prove the language L = {〈M1,M2〉 | M1,M2 are TMs, and L(M1) ⊆
L(M2)} is undecidable.
2
Problem 6 (40 points). Prove that the language L = {〈M〉 | |L(M)| ≤ 5, i.e., L(M) contains 5
strings or less } is Turing unrecognizable.
3