CS3800 Theory of Computation Quiz Sample Questions Emanuele Viola
1. Give the formal definition of a DFA. Give the formal definition of a string w being accepted by a DFA.
2. Give the formal definition of an NFA. Give the formal definition of a string w being accepted by an NFA.
3. Give the formal definition of a regular expression. Give the formal definition of the language described by a regular expression.
4. Givetheformaldefinition(Q,Σ,δ,q0,F)ofthefollowingDFA,andshowthatitaccepts the string aaba according to the formal definition of accepting.
1b a
b
a
2
5. Give the state diagrams of DFAs recognizing each of the following languages over the alphabet Σ = {a,b}.
(a) L1 = {w | w contains an odd number of b’s}
(b) L2 = {w | every a in w is immediately followed by a b}
(c) L3 = {w | every even character in w is equal to w’s first character} (d) L4 = {w | w is any string except aba}
(e) L5 = {w | w ends with bb}
(f) L6 = {w | w contains the substring aaa}
6. Show that if A and B are regular languages, then so are the following languages. For this question you have to work with DFA only; you cannot use the equivalence between DFA and NFA.
(a) not A
(b) AB
(c) AB
(d) A ⊖ B, which is the set of strings w that belong to exactly one of A and B, i.e., (AB)−(AB).
7. Givetheformaldefinition(Q,Σ,δ,q0,F)ofthefollowingNFA,andshowthatitaccepts the string aab according to the formal definition of accepting.
a εa
b
8. Give the state diagrams of NFAs recognizing each of the following languages over the alphabet Σ = {a,b}.
(a) L1 = {w | w contains an even number of a’s or an odd number of b’s} (b) L2 = {w | w begins with anaor ends with ab}
(c) L3 = {w | w = xy, where x only contains a’s and y only contains b’s}
9. Convert each of the following NFAs to an equivalent DFA using the conversion process
seen in class.
aba (a) εa
1
2
3
123 b
(b)
b
a
ε
12 b
10. Give the state diagram of an NFA that recognizes L1 ∪L2, where L1 and L2 are defined over the alphabet Σ = {a,b} as follows:
L1 = {w|thelengthofwisatmost4} L2 = {w | every odd position of w is ab}
11. Give the state diagram of an NFA that recognizes L1 ◦L2, where L1 and L2 are defined over the alphabet Σ = {a,b} as follows:
L1 = {w | w begins with anaand ends with ab}
L2 = {w | w contains exactly two as}
12. Give the state diagram of an NFA that recognizes L∗, where L is defined over the alphabet Σ = {a,b} as follows:
L = {w | w does not contain the substring ab}
13. Convert each of the following regular expressions to an equivalent NFA using the
conversion process seen in class. You need to show each step of the process. R1 =a∗(baa∗)∗ R2 =(a∪b)∗b
14. Give regular expressions that describe each of the following languages over the alphabet Σ = {a,b}.
(a) L1 = {w | every b in w is immediately followed by an a} (b) L2 = {w | w contains the substring bba}
(c) L3 = {w | every even position of w is ana}
(d) L4 = {w | w begins with abor ends with ana}
15. Convert each of the following DFAs to an equivalent regular expression using the conversion process seen in class. You need to show each step of the process.
(a)
(b)
1a2
a,b b
a,b a
b
b
3
12 a
16. State the pumping lemma for regular languages. State the contrapositive of the pump- ing lemma for regular languages.
17. Use the pumping lemma to show that the following languages are not regular.
(a) L1 ={0n1n |n≥0}
(b) L2 ={w|w∈{0,1}∗ andwhasasmany0sas1s}
(c) L3 ={ww|w∈{0,1}∗} (d) L4 ={1n2 |n≥0}
(e) L5 ={0i1j0k |i,j,k≥0andi+j=k}
(f) L6 ={0i1j |i,j≥0andi>j} (g) L7 ={0i1j |i,j≥0and5i
(c) L3 ={x#y|x,y∈{0,1}∗ and|x|̸=|y|}
(d) L4 ={0m1m0n1n |misevenandnisodd}
(e) L5 ={w|w∈{0,1}∗ andwisapalindrome}
(f) L6 ={w|w∈{0,1}∗ andw=w1···wk, k≥1, andeachwi isapalindrome}
(g) L7 = {w#x | w, x ∈ {0, 1}∗ and wR is a substring of x} (Recall that wR denotes the reverse of w; for example, 0001011R = 1101000.)
(h) L8 ={w∈{0,1}∗ |eachprefixofwhasatleastasmany0’sas1’s}
(i) L9 ={w∈{0,1}∗ |whasasmany0’sas1’s}
(j) L10 ={0n12n |n≥0}
(k) L11 ={ambncp |m+n=p}
(l) L12 ={ambncpdq |m+n=p+q}
20. Give the formal definition of an ambiguous context-free grammar. Give the formal definition of a leftmost derivation in a context-free grammar.g
21. Show that the following context-free grammars are ambiguous. (a)S → S+S | S×S | 0 | 1
(b)S → T0T | V1V T→0|1|ǫ V→0|1|ǫ
(c) S → AB
A→ 0A0|1A1|0|1 B → BB | 0 | 1
22. State the pumping lemma for context-free languages. State the contrapositive of the pumping lemma for context-free languages.
23. Use the pumping lemma to show that the following languages are not context-free.
(a) L1 ={anbncn |n≥0} (b) L2 ={0n1n0n1n |n≥0}
(c) L3 ={0i1j2k |i≥j≥k≥0} (d) L4 ={ss|s∈{0,1}∗}
(e) L5 ={aibjck |0≤i≤j≤k}
24. Give a CFG for the language L = {w ∈ {a,b}∗ | w has twice as many a’s as b’s}.
Show that your grammar is correct. For this problem you cannot use PDA.
25. (a) Show that context-free languages are not closed under intersection. (b) Show that context-free languages are not closed under complement.
26. Give the formal definition of a Turing machine.
27. Give the formal definition of a configuration of a Turing machine. Give the formal definition of a configuration yielding another configuration.
28. Give the formal definition of a Turing machine M accepting a string w.
29. Give the formal definition of a Turing machine M deciding a language L. Is your
definition equivalent to the following definition? Why or why not?
“M decides L if the following is true: for all w, M accepts w ⇔ w ∈ L.”
30. Give the high-level description of a Turing machine that decides each of the following languages.
(a) L1 ={anbncn |n≥0}
(b) L2 ={a2n |n≥0}
(c) L3 ={aibjck |i,j,k≥0andi+j=k}
(d) L4 ={wwR |w∈{0,1}∗}
(Recall that wR denotes the reverse of w; for example, 0001011R = 1101000.)
31. Give the formal definition of a computable function.
32. Do JAVA and Turing machines decide the same set of languages? If so, explain why we are using Turing machines instead of JAVA in this class. Name one proof that is easier using Turing machines than using JAVA.
33. State the fact seen in class regarding the locality of Turing machine computation.
34. State the Church-Turing thesis.
35. Give the definition of the language ATM. Prove that ATM is undecidable.
36. Give the formal definition of a reduction from ATM to another language L.
37. Show that each of the following languages is undecidable by reducing ATM to it.
(a) L1 ={M |M isaTuringmachineandL(M)=∅} (b) L2 ={M |M isaTuringmachineandL(M)̸=Σ∗}
(c) L3 = {(M, w) | M is a Turing machine that halts on input w} (d) L4 = {M | M is a Turing machine that accepts input 001}
(e) L5 = {(M,M′) | M and M′ are Turing machines and L(M) ⊆ L(M′)}
38. Give a high-level description of the proof that the following language is undecidable: All-CF = {G | G is a context-free grammar and L(G) = Σ∗}.
39. Assume that All-CF is undecidable, and show that each of the following languages is undecidable.
(a) L1 = {(G, G′) | G and G′ are context-free grammars and L(G) = L(G′)}
(b) L2 = {(G, G′) | G and G′ are context-free grammars and L(G) ∪ L(G′) = Σ∗}
(c) L3 = {(G, G′) | G and G′ are context-free grammars and L(G) ⊆ L(G′)}
40. Give the definition of the language TRUTH seen in class. Give two strings, one that is in TRUTH and one that is not. Give a high-level description of the proof that TRUTH is undecidable.
41. Give the definition of the language H10 seen in class. Give two strings, one that is in H10 and one that is not. Give a high-level description of the proof that H10 is undecidable.
42. Explain how to encode any two strings x, y in {0, 1}∗ as a string (x, y) ∈ {0, 1}∗ such that |(x, y)| ≤ 2 log log(|x|) + log(|x|) + |x| + |y| + 10.
43. (a) Show that the set of incompressible strings is undecidable. (b) Show that K(x) is not computable.
44. For each of the following languages, first give the high-level description of a Turing machine that decides the language, then show an upper bound on the running time of your machine. Your upper bound should be tight up to constant multiplicative factors. In particular, if your machine runs in time n2 and you show an upper bound of n3, that is not sufficient.
(a) L1 ={anbncn |n≥0}
(b) L2 ={a2n |n≥0}
(c) L3 ={aibjck |i,j,k≥0andi+j=k}
(d) L4 ={wwR |w∈{0,1}∗}
(Recall that wR denotes the reverse of w; for example, 0001011R = 1101000.)
(e) L5 ={aibjck |i,j,k≥0andi·j=k}
(f) L6 ={ww|w∈{0,1}∗}
(Hint: Find the middle of the input string. Note that finding the middle is not a trivial operation, and you have to explain how it is accomplished in terms of head movements.)
45. Give the formal definition of each of the following classes of languages.
(a) Time(t(n)) (b) P
(c) NP (d) EXP
46. Show that NP ⊆ EXP. 47. Show that P ̸= EXP.
48. For each of the following classes of languages, say if it remains the same if we were using JAVA as our computational model instead of Turing machines.
(a) Time(n) (b) Time(n2)
(c) P (d) NP
(e) EXP
(f) {L | L is decidable}
49. Give the formal definition of each of the following languages.
(a) 3SAT (b) CLIQUE
(c) SUBSET-SUM (d) 3COLOR
50. Give the formal definition of a polynomial-time reduction from one language to another.
51. Show that there is a polynomial-time reduction from 3SAT to each of the following languages.
(a) CLIQUE
(b) SUBSET-SUM
(c) 3COLOR
(d) INDEPENDENT-SET defined as follows. For a graph G = (V, E) a set of nodes X ⊆ V is an independent set if no two nodes in X share an edge; more formally, X is an independent set if for all u,v ∈ X, (u,v) ̸∈ E.
Then, define INDEPENDENT-SET to be the following language.
INDEPENDENT-SET = {(G, k) | G is a graph that has an independent set of size k} (Hint: modify the reduction from 3SAT to CLIQUE; use the same set of nodes,
but change how the edges are chosen.)
(e) SYSTEM, defined as follows. A linear inequality is an inequality involving sums of variables and constants, such as x + y ≥ z, x ≤ −17, and so on. A system of linear inequalities has an integer solution if it is possible to substitute integer values for the variables so that every inequality in the system becomes true. The language SYSTEM consists of systems of linear inequalities that have an integer solution. For example,
(x + y ≥ z, x ≤ 5, y ≤ 1, z ≥ 5) ∈ SYSTEM (x + y ≥ 2z, x ≤ 5, y ≤ 1, z ≥ 5) ̸∈ SYSTEM
52. Show that each of the following languages is in NP.
(a) 3SAT (b) CLIQUE
(c) SUBSET-SUM (d) 3COLOR
(e) INDEPENDENT-SET (Refer to 51 for the definition of the language.)
53. Without using the Cook-Levin theorem, prove that the following language is NP- complete:
L = {(M,x,1t) : M is a Turing machine : ∃y ∈ {0,1}t : M(x,y) accepts within t time steps}.
54. State the Cook-Levin theorem.
55. Give the formal definition that a language L is NP-complete.
56. (For this problem you may use the Cook-Levin theorem without giving a proof.) Let L be a language that satisfies the following.
(a) L ∈ NP.
(b) There is a polynomial-time reduction from 3SAT to L.
Show that L is NP-complete.
57. Give a high-level description of the proof of the Cook-Levin theorem.
58. Define Regular Expressions with Exponentiation (REE). In what way is exponentiation useful in proving that the language All-REE = {R | R is an REE and L(R) = Σ∗} is not in P?
59. For each of the following results, say if the corresponding proof seen in class exploited the locality of Turing machines.
(a) ATM is undecidable.
(b) {(M, w) | M is a Turing machine that halts on input w} is undecidable.
(c) All-CF = {G | G is a context-free grammar and L(G) = Σ∗} is undecidable. (d) All-REE={R|RisanREEandL(R)=Σ∗}isnotinP.
(e) The Cook-Levin theorem.
60. Show that NTIME(n2) ⊆ P ⇒ P = NP. Hint: use padding.
61. Show that if Σ2P = Π2P then for every i ≥ 3,ΣiP = Σ2P.
62. Let L = {φ : φ has at least two satisfying assignments}. Show that P = NP ⇒ L ∈ P.
63. Let L be a language. Suppose L ∈ RP and (notL) ∈ RP. Give a randomized Turing machine M for L that satisfies the following conditions:
• for every input x and for every R, M(x,R) either outputs the correct answer or outputs “?”,
• for every x, PrR[M(x,R) =?] ≤ 1/2, and • M(x,R) runs in time polynomial in |x|.
Then explain how the constant 1/2 can be replaced with 2−|x|.