The Australian National University
First Semester Examination May 27, 2022
Theory of Computation Final Exam
Writing Period: 150 minutes Study Period: 15 minutes Permitted Materials: None
Please read the following instructions carefully.
• This is a closed book exam.
No material other than the provided scratch paper is permitted.
• Use either a black or a blue pen. Use the space provided. Marks may be lost for giving information that is irrelevant.
• Please write your student number on every sheet of paper.
• This exam consists of 7 questions worth a total of 150 points
(about 1 point per minute).
• This examination paper is confidential and is not to be taken from the examination room.
Student Number
For official use only:
Q1 Q2 Q3 Q4 Q5 Q6 Q7 Total
40 25 15 15 20 10 25 150
Code Help
Question 1 True or False – With Justification (40 points)
Please read each of the following statements very carefully, some of them are trying to trick you. For each of the statements, state whether it is true or false and justify your answer in 1–2 sentences. Each correct answer gives 1 point and each correct justification gives 3 additional points.
(a) The union of infinitely many regular languages is regular.
(b) For a regular language L containing exactly n strings, there is a nondeterministic finite automaton with at most n states that accepts L.
(c) If a language fulfills the condition of the pumping lemma, then it is regular.
(d) If a context-free grammar has no unit productions and no ε-productions, then for any given string, the height of all parse trees of that string is bounded.
(e) The language L = {(M, w) | M does not accept w} is recursively enumerable.
(f) If a language L is recursively enumerable and its complement Lc is recursively enumerable, then L is decidable.
(g) There are undecidable languages over the alphabet containing only one symbol.
(h) P is known to be closed under intersection.
(i) NP is the set of all problems that do not have a polynomial-time algorithm.
(j) If L1 is NP-complete, L2 is NP and L1 ≤P L2, then L2 is NP-complete.
Question 2 Finite Automata and Regular Expressions 5 + 10 + 10 points Consider the following finite automaton A over the alphabet Σ = {a, b, c}.
q0 a q3a,b ab
(a) Is A deterministic? If not, convert A into a DFA.
(b) Is A minimal? If not, convert A into a minimal DFA.
(c) Convert A into a regular expression.
Question 3 Decidability 20 points Consider the language
L = {M | M is a Turing machine that has at least one unreachable state }. Prove that L is undecidable.
Question 4 NP-Completeness 10 points Explain in 3–4 clear English sentences why NP-complete problems are considered intractable.
Question 5 Proving NP-Completeness 5 + 20 points Consider the subgraph-isomorphism problem: given two graphs G1 = (V1, E1) and G2 = (V2, E2), does G1
contain a copy of G2 as a subgraph? I.e., is there a subset U ⊆ V1 and a function i : U → V2 such that (v1,v2)∈E1∩(U×U) ⇐⇒ (i(v1),i(v2))∈E2?
(a) Prove that the subgraph-isomorphism problem is in NP.
(b) The k-clique problem is the question whether a given graph G = (V, E) has a subset of vertices C ⊆ V
such that C has at least k elements and every two vertices in C are connected with an edge in G.
Show that the clique problem can be reduced to the subgraph-isomorphism problem: Give a polynomial-time computable function f such that G has a k-clique if and only if G2 is a subgraph of G1 for (G1,G2) = f(G). (Hint: choose G2 to be the complete graph with k vertices.)
Computer Science Tutoring
Question 6 PSPACE = NPSPACE vs P = NP 10 points
Explain in 3–4 clear English sentences why P =? NP question is more difficult to decide than PSPACE =? NPSPACE?
Question 7 Error Reduction of RP 25 points Let L ⊆ Σ∗ be such that there exists a polynomial-time probabilistic Turing machine (PTM) M satisfying
foreveryw∈Σ∗:(1)Ifw∈L,thenPr[M acceptsw]≥n−c and(2)ifw∈/L,thenPr[M acceptsw]=0. Prove that for every d > 0 there exists a polynomial-time PTM M′ such that for every w ∈ Σ∗, (1) if
w∈LthenPr[M acceptsw]≥1−2−nd,and(2)ifw∈/LthenPr[M acceptsw]=0.
程序代写 CS代考 加QQ: 749389476