practice-final-soln.dvi
Practice Problems for Final Exam: Solutions
CS 341: Foundations of Computer Science II
Prof. Marvin K. Nakayama
1. Short answers:
(a) Define the following terms and concepts:
i. Union, intersection, set concatenation, Kleene-star, set subtraction, complement
Answer: Union: S ∪ T = { x | x ∈ S or x ∈ T}
Intersection: S ∩ T = { x | x ∈ S and x ∈ T}
Concatenation: S ◦ T = { xy | x ∈ S, y ∈ T}
Kleene-star: S∗ = { w1w2 · · ·wk | k ≥ 0, wi ∈ S ∀ i = 1, 2, . . . , k}
Subtraction: S − T = { x | x ∈ S, x 6∈ T}
Complement: S = { x ∈ Ω | x 6∈ S} = Ω− S, where Ω is the universe of all elements under
consideration.
ii. A set S is closed under an operation f
Answer: S is closed under f if applying f to members of S always returns a member of S.
iii. Regular language
Answer: A regular language is defined by a DFA.
iv. Kleene’s theorem
Answer: A language is regular if and only if it has a regular expression.
v. Context-free language
Answer: A CFL is defined by a CFG.
vi. Chomsky normal form
Answer: A CFG is in Chomsky normal form if each of its rules has one of 3 forms: A → BC,
A → x, or S → ε, where A,B,C are variables, B and C are not the start variable, x is a
terminal, and S is the start variable.
vii. Church-Turing Thesis
Answer: The informal notion of algorithm corresponds exactly to a Turing machine that
always halts (i.e., a decider).
viii. Turing-decidable language
Answer: A language A that is decided by a Turing machine; i.e., there is a Turing machine
M such that M halts and accepts on any input w ∈ A, and M halts and rejects on input
input w 6∈ A; i.e., looping cannot happen.
ix. Turing-recognizable language
Answer: A language A that is recognized by a Turing machine; i.e., there is a Turing
machine M such that M halts and accepts on any input w ∈ A, and M rejects or loops on
any input w 6∈ A.
x. co-Turing-recognizable language
Answer: A language whose complement is Turing-recognizable.
1
xi. Countable and uncountable sets
Answer: A set S is countable if it is finite or we can define a correspondence between S and
the positive integers. In other words, we can create a list of all the elements in S and each
specific element will eventually appear in the list. An uncountable set is a set that is not
countable. A common approach to prove a set is uncountable is by using a diagonalization
argument.
xii. Language A is mapping reducible to language B, A ≤m B
Answer: Suppose A is a language defined over alphabet Σ1, and B is a language defined
over alphabet Σ2. Then A ≤m B means there is a computable function f : Σ
∗
1 → Σ
∗
2 such
that w ∈ A if and only if f(w) ∈ B. Thus, if A ≤m B, we can determine if a string w
belongs to A by checking if f(w) belongs to B.
Σ
∗
1
Σ
∗
2
A
B
f
f
w ∈ A ⇐⇒ f(w) ∈ B
YES instance for problem A ⇐⇒ YES instance for problem B
xiii. Function f(n) is O(g(n))
Answer: There exist constants c and n0 such that |f(n)| ≤ c · g(n) for all n ≥ n0.
xiv. Classes P and NP
Answer: P is the class of languages that can be decided by a deterministic Turing
machine in polynomial time. NP is the class of languages that can be verified in (de-
terministic) polynomial time. Equivalently, NP is the class of languages that can be
decided by a nondeterministic Turing machine in polynomial time.
xv. Language A is polynomial-time mapping reducible to language B, A ≤P B.
Answer: Suppose A is a language defined over alphabet Σ1, and B is a language defined
over alphabet Σ2. Then A ≤P B means there is a polynomial-time computable function
f : Σ∗1 → Σ
∗
2 such that w ∈ A if and only if f(w) ∈ B.
xvi. NP-complete
Answer: Language B is NP-Complete if B ∈ NP, and for every language A ∈ NP, we have
A ≤P B.
A1
A2
A3 A4
A5
B
NP
2
The typical approach to proving a language C is NP-Complete is as follows:
• First show C ∈ NP by giving a deterministic polynomial-time verifier for C. (Alterna-
tively, we can show C ∈ NP by giving a nondeterministic polynomial-time decider for
C.)
• Next show that a known NP-Complete language B can be reduced to C in polynomial
time; i.e., B ≤P C.
A1
A2
A3 A4
A5
B
NP
C
Note that the second step implies that A ≤P C for each A ∈ NP Because we can first reduce
A to B in polynomial time because B is NP-Complete, and then we can reduce B to C in
polynomial time, so the entire reduction of A to C takes polynomial time.
xvii. NP-hard
Answer: Language B is NP-hard if for every language A ∈ NP, we have A ≤P B.
(b) Give the transition functions δ of a DFA, NFA, PDA, Turing machine and nondeterministic
Turing machine.
Answer:
• DFA, δ : Q× Σ → Q, where Q is the set of states and Σ is the alphabet.
• NFA, δ : Q× Σε → P(Q), where Σε = Σ ∪ {ε} and P(Q) is the power set of Q
• PDA, δ : Q× Σε × Γε → P(Q× Γε), where Γ is the stack alphabet and Γε = Γ ∪ {ε}.
• Turing machine, δ : Q× Γ → Q× Γ× {L,R}, where Γ is the tape alphabet, L means move
tape head one cell left, and R means move tape head one cell right.
• Nondeterministic Turing machine, δ : Q × Γ → P(Q × Γ × {L,R}), where Γ is the tape
alphabet, L means move tape head one cell left, and R means move tape head one cell right.
(c) Explain the “P vs. NP” problem.
Answer: P is the class of languages that can be solved in polynomial time, and NP is the class
of languages that can be verified in polynomial time. We know that P ⊆ NP, but it is currently
unknown if P = NP or P 6= NP.
2. Recall that ATM = { 〈M,w〉 | M is a TM that accepts string w }.
(a) Prove that ATM is undecidable. You may not cite any theorems or corollaries in your proof.
Overview of Proof: We use a proof by contradiction. Suppose ATM is decided by some TM
H, so H accepts 〈M,w〉 if TM M accepts w, and H rejects 〈M,w〉 if TM M doesn’t accept w.
H−→〈M,w〉 ✟
✟
✟
✟✯
❍
❍
❍
❍❥
accept, if 〈M,w〉 ∈ A
TM
reject, if 〈M,w〉 6∈ A
TM
3
Define another TM D using H as a subroutine.
HH
D
−→〈M, 〈M〉〉 ✟
✟
✟
✟✯
❍
❍
❍
❍❥
accept
reject
−→〈M〉
✟
✟
✟
✟
✟
✟
✟
✟
✟✯❍
❍
❍
❍
❍
❍
❍
❍
❍❥
accept
reject
So D takes as input any encoded TM 〈M〉, then feeds 〈M, 〈M〉〉 as input into H, and finally
outputs the opposite of what H outputs. Because D is a TM, we can feed 〈D〉 as input into D.
What happens when we run D with input 〈D〉?
HH
D
−→〈D, 〈D〉〉 ✟
✟
✟
✟✯
❍
❍
❍
❍❥
accept
reject
−→〈D〉
✟
✟
✟
✟
✟
✟
✟
✟
✟✯❍
❍
❍
❍
❍
❍
❍
❍
❍❥
accept
reject
Note that D accepts 〈D〉 iff D doesn’t accept 〈D〉, which is impossible. Thus, ATM must be
undecidable.
Complete Proof: Suppose there exists a TM H that decides ATM. TM H takes input 〈M,w〉,
where M is a TM and w is a string. If TM M accepts string w, then 〈M,w〉 ∈ ATM and H
accepts input 〈M,w〉. If TM M does not accept string w, then 〈M,w〉 6∈ ATM and H rejects
input 〈M,w〉. Consider the language L = { 〈M〉 | M is a TM that does not accept 〈M〉 }. Now
construct a TM D for L using TM H as a subroutine:
D = “On input 〈M〉, where M is a TM:
1. Run H on input 〈M, 〈M〉〉.
2. If H accepts, reject. If H rejects, accept .”
If we run TM D on input 〈D〉, then D accepts 〈D〉 if and only if D doesn’t accept 〈D〉. Because
this is impossible, TM H must not exist, so ATM is undecidable.
(b) Show that ATM is Turing-recognizable.
Answer: The universal TM U recognizes ATM, where U is defined as follows:
U = “On input 〈M,w〉, where M is a TM and w is a string:
1. Run M on w.
2. If M accepts w, accept ; if M rejects w, reject.”
Note that U only recognizes ATM and does not decide ATM Because when we run M on w,
there is the possibility that M neither accepts nor rejects w but rather loops on w.
3. Each of the languages below in parts (a), (b), (c), (d) is of one of the following types:
Type REG. It is regular.
Type CFL. It is context-free, but not regular.
Type DEC. It is Turing-decidable, but not context-free.
For each of the following languages, specify which type it is. Also, follow these instructions:
4
• If a language L is of Type REG, give a regular expression and a DFA (5-tuple) for L.
• If a language L is of Type CFL, give a context-free grammar (4-tuple) and a PDA (6-tuple) for
L. Also, prove that L is not regular.
• If a language L is of Type DEC, give a description of a Turing machine that decides L. Also,
prove that L is not context-free.
(a) A = {w ∈ Σ∗ | w = reverse(w) and the length of w is divisible by 4 }, where Σ = {0, 1}.
Circle one type: REG CFL DEC
Answer: A is of type CFL. A CFG G = (V,Σ, R, S) for A has V = {S}, Σ = {0, 1}, starting
variable S, and rules R = {S → 00S00 | 01S10 | 10S01 | 11S11 | ε }. A PDA for A is as follows:
q1 q2
q3
q4
q5
q6
ε, ε → $
0, ε → 0
1, ε → 1
0, ε → 0
1, ε → 1
ε, ε → ε
0, 0 → ε
1, 1 → ε
0, 0 → ε
1, 1 → ε
ε, $ → ε
The above PDA has 6-tuple (Q,Σ,Γ, δ, q1, F ), with Q = {q1, q2, . . . , q6}, Σ = {0, 1}, Γ =
{0, 1, $}, starting state q1, F = {q1, q6}, and transition function δ : Q × Σε × Γε → P(Q× Γε)
defined by
Input: 0 1 ε
Stack: 0 1 $ ε 0 1 $ ε 0 1 $ ε
q1 { (q2, $) }
q2 { (q3, 0) } { (q3, 1) } { (q4, ε) }
q3 { (q2, 0) } { (q2, 1) }
q4 { (q5, ε) } { (q5, ε) } {(q6, ε)}
q5 { (q4, ε) } { (q4, ε) }
q6
Blank entries are ∅.
We now prove that A is not regular by contradiction. Suppose that A is regular. Let p ≥ 1 be
the pumping length of the pumping lemma (Theorem 1.I). Consider string s = 0p 12p 0p ∈ A,
and note that |s| = 4p > p, so the conclusions of the pumping lemma must hold. Thus, we can
split s = xyz satisfying conditions (1) xyiz ∈ A for all i ≥ 0, (2) |y| > 0, and (3) |xy| ≤ p.
Because all of the first p symbols of s are 0s, (3) implies that x and y must only consist of 0s.
Also, z must consist of the rest of the 0s at the beginning, followed by 12p0p. Hence, we can write
x = 0j , y = 0k, z = 0m 12p 0p, where j+k+m = p because s = 0p12p0p = xyz = 0j 0k 0m 12p 0p.
Moreover, (2) implies that k > 0. Finally, (1) states that xyyz must belong to A. However,
xyyz = 0j 0k 0k 0m 12p 0p = 0p+k 12p 0p
because j+k+m = p. But, k > 0 implies reverse(xyyz) 6= xyyz, which means xyyz 6∈ A, which
contradicts (1). Therefore, A is a nonregular language.
5
(b) B = { bnanbn | n ≥ 0 }.
Circle one type: REG CFL DEC
Answer: B is of type DEC. Below is a description of a Turing machine that decides B.
M = “On input string w ∈ {a, b}∗:
1. Scan the input from left to right to make sure that
it is a member of b∗a∗b∗, and reject if it isn’t.
2. Return tape head to left-hand end of tape.
3. Repeat the following until there are no more bs left on the tape.
4. Replace the leftmost b with x.
5. Scan right until an a occurs. If there are no a’s, reject.
6. Replace the leftmost a with x.
7. Scan right until a b occurs. If there are no b’s, reject.
8. Replace the leftmost b (after the a’s) with x.
9. Return tape head to left-hand end of tape, and go to stage 3.
10. If the tape contains any a’s, reject. Otherwise, accept.”
We now prove that B is not context-free by contradiction. Suppose that B is context-free. Let
p be the pumping length of the pumping lemma for CFLs (Theorem 2.D), and consider string
s = bpapbp ∈ B. Note that |s| = 3p > p, so the pumping lemma will hold. Thus, we can split
s = bpapbp = uvxyz satisfying uvixyiz ∈ B for all i ≥ 0, |vy| ≥ 1, and |vxy| ≤ p. We now
consider all of the possible choices for v and y:
• Suppose strings v and y are uniform (e.g., v = bj for some j ≥ 0, and y = ak for some
k ≥ 0). Then |vy| ≥ 1 implies that v 6= ε or y 6= ε (or both), so uv2xy2z won’t have
the correct number of b’s at the beginning, a’s in the middle, and b’s at the end. Hence,
uv2xy2z 6∈ B.
• Now suppose strings v and y are not both uniform. Then uv2xy2z will not have the form
b · · · ba · · · ab · · · b. Hence, uv2xy2z 6∈ B.
Thus, there are no options for v and y such that uvixyiz ∈ B for all i ≥ 0. This is a contradiction,
so B is not a CFL.
(c) C = {w ∈ Σ∗ | na(w) mod 4 = 1 }, where Σ = {a, b} and na(w) is the number of a’s in string
w. For example, na(babaabb) = 3. Also, recall j mod k returns the remainder after dividing j
by k, e.g., 3 mod 4 = 3, and 9 mod 4 = 1.
Circle one type: REG CFL DEC
Answer: C is of type REG. A regular expression for C is (b∗ab∗ab∗ab∗ab∗)∗b∗ab∗, and a DFA
for C is below:
6
q1 q2
q3q4
a
b
a
b
a
b
a
b
The above DFA has 5-tuple (Q,Σ, δ, q1, F ), with Q = {q1, q2, q3, q4}, Σ = {a, b}, q1 as the
starting state, F = {q2}, and transition function δ : Q×Σ → Q defined by
a b
q1 q2 q1
q2 q3 q2
q3 q4 q3
q4 q1 q4
(d) D = { bnanbkck | n ≥ 0, k ≥ 0 }. [Hint: Recall that the class of context-free languages is closed
under concatenation.]
Circle one type: REG CFL DEC
Answer: D is of type CFL. A CFG G = (V,Σ, R, S) for D has V = {S,X, Y }, Σ = {a, b, c},
S as the starting variable, and rules R:
S → XY
X → bXa | ε
Y → bY c | ε
A PDA for D is below:
q1 q2 q3 q4 q5 q6
ε, ε → $ ε, ε → ε
b, ε → b a, b → ε
ε, $ → $
b, ε → b
ε, ε → ε
c, b → ε
ε, $ → ε
We formally express the PDA as a 6-tuple (Q,Σ,Γ, δ, q1, F ), where Q = {q1, q2, . . . , q6}, Σ =
{a, b, c}, Γ = {b, $} (use $ to mark bottom of stack), q1 is the start state, F = {q6}, and the
transition function δ : Q× Σε × Γε → P(Q× Γε) is defined by
7
Input: a b c ε
Stack: b $ ε b $ ε b $ ε b $ ε
q1 { (q2, $) }
q2 { (q2, b) } { (q3, ε) }
q3 { (q3, ε) } { (q4, $) }
q4 { (q4, b) } { (q5, ε) }
q5 { (q5, ε) } { (q6, ε) }
q6
Blank entries are ∅.
An important point to note about the above PDA is that the transition from q3 to q4 pops and
pushes $. It is important to pop $ to make sure that the number of a’s matches the number of
b’s in the beginning. We need to push $ to mark the bottom of the stack again for the second
part of the string of b’s and c’s.
We now prove that D is not regular by contradiction. Suppose that D is regular. Let p ≥ 1 be
the pumping length of the pumping lemma (Theorem 1.I). Consider string s = bp ap bp cp ∈ D,
and note that |s| = 4p > p, so the conclusions of the pumping lemma must hold. Thus, we can
split s = xyz satisfying (1) xyiz ∈ D for all i ≥ 0, (2) |y| > 0, and (3) |xy| ≤ p. Because all of
the first p symbols of s are b’s, (3) implies that x and y must only consist of b’s. Also, z must
consist of the rest of the b’s at the beginning, followed by ap bp cp. Hence, we can write x = bj ,
y = bk, z = bm ap bp cp, where j + k+m = p because s = bp ap bp cp = xyz = bj bk bm ap bp cp.
Moreover, (2) implies that k > 0. Finally, (1) states that xyyz must belong to D. However,
xyyz = bj bk bk bm ap bp cp = bp+k ap bp cp
because j + k + m = p. Also k > 0, so xyyz 6∈ D, which contradicts (1). Therefore, D is a
nonregular language.
4. Each of the languages below in parts (a), (b), (c), (d) is of one of the following types:
Type DEC. It is Turing-decidable.
Type TMR. It is Turing-recognizable, but not decidable.
Type NTR. It is not Turing-recognizable.
For each of the following languages, specify which type it is. Also, follow these instructions:
• If a language L is of Type DEC, give a description of a Turing machine that decides L.
• If a language L is of Type TMR, give a description of a Turing machine that recognizes L.
Also, prove that L is not decidable.
• If a language L is of Type NTR, give a proof that it is not Turing-recognizable.
In each part below, if you need to prove that the given language L is decidable, undecidable, or not
Turing-recognizable, you must give an explicit proof of this; i.e., do not just cite a theorem that
establishes this without a proof. However, if in your proof you need to show another language L′
has a particular property and there is a theorem that establishes this, then you may simply cite the
theorem for L′ without proof.
(a) EQTM = { 〈M1,M2〉 | M1,M2 are TMs with L(M1) = L(M2) }. [Hint: show ATM ≤m EQTM.]
Circle one type: DEC TMR NTR
Answer: EQTM is of type NTR (see Theorem 5.K). We prove this by showing ATM ≤m EQTM
and applying Corollary 5.I. Define the reducing function f(〈M,w〉) = 〈M1,M2〉, where
8
• M1 = “reject on all inputs.”
• M2 = “On input x:
1. Ignore input x, and run M on w.
2. If M accepts w, accept .”
Note that L(M1) = ∅. For the language of TM M2,
• if M accepts w (i.e., 〈M,w〉 6∈ ATM), then L(M2) = Σ
∗;
• if M does not accept w (i.e., 〈M,w〉 ∈ ATM), then L(M2) = ∅.
Thus, if 〈M,w〉 is a YES instance for ATM (i.e., 〈M,w〉 ∈ ATM, so M does not accept w), then
L(M1) = ∅ and L(M2) = ∅, which are the same, implying that f(〈M,w〉) = 〈M1,M2〉 ∈ EQTM
is a YES instance for EQTM. Also, if 〈M,w〉 is a NO instance for ATM (i.e., 〈M,w〉 6∈ ATM,
so M accepts w), then L(M1) = ∅ and L(M2) = Σ
∗, which are not the same, implying that
f(〈M,w〉) = 〈M1,M2〉 6∈ EQTM is a NO instance for EQTM. Hence, we see that 〈M,w〉 ∈ ATM
⇐⇒ f(〈M,w〉) = 〈M1,M2〉 ∈ EQTM, so ATM ≤m EQTM. But ATM is not TM-recognizable
(Corollary 4.M), so EQTM is not TM-recognizable by Corollary 5.I.
(b) HALTTM = { 〈M,w〉 | M is a TM that halts on input w }. [Hint: modify the universal TM to
show that HALTTM is Turing-recognizable.]
Circle one type: DEC TMR NTR
Answer: HALTTM is of type TMR (see Theorem 5.A). The following Turing machine recog-
nizes HALTTM:
T = “On input 〈M,w〉, where M is a TM and w is a string:
1. Run M on w.
2. If M halts on w, accept .”
We now prove that HALTTM is undecidable, which is Theorem 5.A. Suppose there exists a TM
R that decides HALTTM. Then we could use R to develop a TM S to decide ATM by modifying
the universal TM to first use R to see if it’s safe to run M on w.
S = “On input 〈M,w〉, where M is a TM and w is a string:
1. Run R on input 〈M,w〉.
2. If R rejects, reject.
3. If R accepts, simulate M on input w until it halts.
4. If M accepts, accept ; otherwise, reject.”
Because TM R is a decider, TM S always halts and is a decider. Thus, deciding ATM is reduced
to deciding HALTTM. However, ATM is undecidable (Theorem 4.I), so that must mean that
HALTTM is also undecidable.
(c) EQDFA = { 〈M1,M2〉 | M1,M2 are DFAs with L(M1) = L(M2) }.
Circle one type: DEC TMR NTR
9
Answer: EQDFA is of type DEC (see Theorem 4.E). The following TM decides EQDFA:
M = “On input 〈A,B〉, where A and B are DFAs:
0. Check if 〈A,B〉 is a proper encoding of 2 DFAs. If not, reject.
1. Construct DFA C such that
L(C) = [L(A) ∩ L(B)] ∪ [L(A) ∩ L(B)]
using algorithms for DFA union, intersection and complementation.
2. Run TM decider for EDFA (Theorem 4.D) on 〈C〉.
3. If 〈C〉 ∈ EDFA, accept ; if 〈C〉 6∈ EDFA, reject.”
(d) ATM, where ATM = { 〈M,w〉 | M is a TM that accepts string w }.
Circle one type: DEC TMR NTR
Answer: ATM is of type NTR, which is just Theorem 4.M. We prove this as follows. We
know that ATM is recognized by the universal Turing machine, so ATM is Turing-recognizable.
If ATM were Turing-recognizable, then ATM is co-Turing-recognizable. This makes ATM both
Turing-recognizable and co-Turing-recognizable. But then Theorem 4.L would imply that ATM
is decidable, which we know is not true by Theorem 4.I. Hence, ATM is not Turing-recognizable.
5. Let L1, L2, L3, . . . be an infinite sequence of regular languages, each of which is defined over a common
input alphabet Σ. Let L = ∪∞
k=1Lk be the infinite union of L1, L2, L3, . . .. Is it always the case
that L is a regular language? If your answer is YES, give a proof. If your answer is NO, give a
counterexample. Explain your answer. [Hint: Consider, for each k ≥ 0, the language Lk = {a
kbk}.]
Answer: The answer is NO. For each k ≥ 1, let Lk = {a
kbk}, so Lk is a language consisting of
just a single string akbk. Because Lk is finite, it must be a regular language by Theorem 1.F. But
L = ∪∞
k=1Lk = { a
kbk | k ≥ 1 }, which we know is not regular (see end of Chapter 1).
6. Let L1, L2, and L3 be languages defined over the alphabet Σ = {a, b}, where
• L1 consists of all possible strings over Σ except the strings w1, w2, . . . , w100; i.e., start with all
possible strings over the alphabet, take out 100 particular strings, and the remaining strings
form the language L1;
• L2 is recognized by an NFA; and
• L3 is recognized by a PDA.
Prove that (L1 ∩ L2)L3 is a context-free language. [Hint: First show that L1 and L2 are regular.
Also, consider L1, the complement of L1.]
Answer: Note that L1 = {w1, w2, . . . , w100}, so |L1| = 100. Thus, L1 is a regular language because
it is finite by Theorem 1.F. Then Theorem 1.H implies that the complement of L1 must be regular,
but the complement of L1 is L1. Thus, L1 is regular. Language L2 has an NFA, so it also has a
DFA by Theorem 1.C. Therefore, L2 is regular. Because L1 and L2 are regular, L1 ∩ L2 must be
regular by Theorem 1.G. Theorem 2.B then implies that L1 ∩ L2 is context-free. Because L3 has a
PDA, L3 is context-free by Theorem 2.C. Hence, because L1∩L2 and L3 are both context-free, their
concatenation is context-free by Theorem 2.F.
10
7. Write Y or N in the entries of the table below to indicate which classes of languages are closed under
which operations.
Regular Decidable Turing-recognizable
Operation languages CFLs languages languages
Union Y (Thm 1.A) Y (Thm 2.E) Y (HW 7, prob 2a) Y (HW 7, prob 2b)
Intersection Y (Thm 1.G) N (HW 6, prob 2a) Y Y
Complementation Y (Thm 1.H) N (HW 6, prob 2b) Y N (e.g., ATM)
We now prove the three “Y” entries that we haven’t established before. We first prove the class of
decidable languages is closed under intersection. Suppose a TM M1 decides language L1, and a TM
M2 decides language L2. Then the following TM decides L1 ∩ L2:
M ′ = “On input string w:
1. Run M1 on input w, and run M2 on input w.
2. If both M1 and M2 accept, accept. Otherwise, reject.
M ′ accepts w if both M1 and M2 accept it. If either rejects, M
′ rejects. The key here is that in
stage 1 of M ′, both M1 and M2 are guaranteed to halt because both are deciders, so M
′ will also
always halt, making it a decider. (Alternatively, we can change stage 1 to run M1 and M2 in parallel
(alternating steps), both on input w, but this isn’t necessary because M1 and M2 are deciders. In
contrast, when we proved that the class of Turing-recognizable languages is closed under union, we
did need to run M1 and M2 in parallel, both on input w, because if we didn’t, then M1 might loop
forever on w, but M2 might accept w.)
We now prove the class of decidable languages is closed under complementation. Suppose a TM M
decides language L. Now create another TM M ′ that just swaps the accept and reject states of M .
Because M is a decider, it always halts, so then M ′ also always halts. Thus, M ′ decides L.
We now prove the class of Turing-recognizable languages is closed under intersection. Suppose a TM
M1 recognizes language L1, and a TM M2 recognizes language L2. Then the following TM recognizes
L1 ∩ L2:
M ′ = “On input string w:
1. Run M1 on input w, and run M2 on input w.
2. If both M1 and M2 accept, accept. Otherwise, reject.
M ′ accepts w if both M1 and M2 accept it. If either rejects, M
′ rejects. But note that if M1 or M2
loops on w, then M ′ also loops on w. Hence, M ′ recognizes L1 ∩ L2 but doesn’t necessarily decide
L1 ∩ L2.
8. Consider the following context-free grammar G in Chomsky normal form:
S → a | Y Z
Z → ZY | a
Y → b | ZZ | Y Y
Use the CYK (dynamic programming) algorithm to fill in the following table to determine if G
generates the string babba. Does G generate babba?
11
1 2 3 4 5
1 Y S S S Y
2 S,Z Z Z Y
3 Y Y S
4 Y S
5 S,Z
b a b b a
No, G does not generate babba because S is not in the upper right corner.
9. Recall that
CLIQUE = { 〈G, k〉 | G is an undirected graph with a k-clique },
3SAT = { 〈φ〉 | φ is a satisfiable 3cnf-function }.
Show that CLIQUE is NP-Complete by showing that CLIQUE ∈ NP and 3SAT ≤P CLIQUE .
Explain your reduction for the general case and not just for a specific example. Be sure to prove
your reduction works and that it requires polynomial time. Also, be sure to provide proofs of these
results, and don’t just cite a theorem.
Answer:
Step 1: show that CLIQUE ∈ NP. We accomplish by giving a polynomial-time verifier for CLIQUE .
The following verifier V for CLIQUE uses the k-clique as the certificate c.
V = “On input 〈〈G, k〉, c〉:
1. Test whether c is a set of k different nodes in G.
2. Test whether G contains all edges connecting nodes in c.
3. If both tests pass, accept ; otherwise, reject.”
We now show that the verifier V runs in deterministic polynomial time in the size of 〈G, k〉. First
we need to measure the size of the encoding 〈G, k〉, which depends on the particular graph G and
the encoding scheme. Suppose the graph G has m nodes, and assume that G is encoded as a list of
nodes followed by a list of edges. To determine the size of the encoding 〈G〉 of the graph G, note that
each edge in G corresponds to a pair of nodes, so G has O(m2) edges. Therefore, the size of 〈G〉 is
m+O(m2) = O(m2), but because we don’t care about polynomial differences, we can simply measure
the size of the 〈G〉 as m. Now we analyze the time complexity of V . In Stage 1, for each of the k
nodes in c, we have to go through the m nodes in G, so Stage 1 of V takes O(k)O(m) = O(km) time.
For Stage 2, for each of the
(
k
2
)
= k(k − 1)/2 = O(k2) pairs of nodes in c that we have to consider,
we have to go through the list of O(m2) edges of G, so Stage 2 takes O(k2)O(m2) = O(k2m2) time.
Thus, the verifier V runs in (deterministic) polynomial time.
Step 2: show that 3SAT ≤m CLIQUE . Next we show how to reduce 3SAT to CLIQUE . We need to
convert an instance of the 3SAT problem to an instance of the CLIQUE problem, with the property
that a YES instance for 3SAT maps to a YES instance of CLIQUE , and a NO instance for 3SAT
maps to a NO instance of CLIQUE . An instance of 3SAT is a 3cnf-formula φ, and φ is a YES
instance for 3SAT if φ is satisfiable, and φ is a NO instance for 3SAT if φ is not satisfiable. An
instance of CLIQUE is a pair 〈G, k〉 of a graph G and an integer k, and 〈G, k〉 is a YES instance for
12
CLIQUE if G has a clique of size k, and 〈G, k〉 is a NO instance for CLIQUE if G doesn’t have a
clique of size k. Thus, the reduction needs to map each 3cnf-formula to a graph and number k.
The reduction works as follows. Suppose that φ is a 3cnf-formula with k clauses. From φ, construct
a graph G having a node for each literal in φ. Arrange the nodes in triples, where each triple
corresponds to the literals from one clause. Add edges between every pair of nodes in G except when
the nodes are from the same triple, or when the nodes are contradictory, e.g., xi and xi.
To prove that this mapping is indeed a reduction, we need to show that 〈φ〉 ∈ 3SAT if and only if
〈G, k〉 ∈ CLIQUE . Note that φ is satisfiable if and only if every clause has at least one true literal.
Suppose φ is satisfiable, so it is a YES instance for 3SAT . For each triple of nodes, choose a node
corresponding to a true literal in the corresponding clause. This results in choosing k nodes, with
exactly one node from each triple. This collection of k nodes is a k-clique because the graph G has
edges between every pair of nodes except those in the same triple and not between contradictory
literals. Thus, the resulting graph and number k is a YES instance for CLIQUE , so 〈φ〉 ∈ 3SAT
implies 〈G, k〉 ∈ CLIQUE .
Now we show the converse: each NO instance for 3SAT maps to a NO instance for CLIQUE , which
is equivalent to 〈G, k〉 ∈ CLIQUE implying that 〈φ〉 ∈ 3SAT . Suppose that G has a k-clique. The
k nodes must be from k different triples because G has no edges between nodes in the same triple.
Thus, the k literals corresponding to the k nodes in the k-clique come from k different clauses. Also,
because G does not have edges between contradictory literals, setting the literals corresponding to
the k nodes to true will lead to φ evaluating to true, so 〈φ〉 ∈ 3SAT . Thus, 〈G, k〉 ∈ CLIQUE implies
〈φ〉 ∈ 3SAT . Combining this with the proof from the last paragraph, we have shown 〈φ〉 ∈ 3SAT if
and only if 〈G, k〉 ∈ CLIQUE , so our approach for converting an instance of the 3SAT problem into
an instance of the CLIQUE problem is indeed a reduction; i.e., 3SAT ≤m CLIQUE .
Step 3: show that reduction 3SAT ≤m CLIQUE takes polynomial time. In other words, we have
to show that the time to convert an instance 〈φ〉 of the 3SAT problem to an instance 〈G, k〉 of
the CLIQUE problem is polynomial in the size of the 3cnf-formula φ. We can measure the size
of φ in terms of its number k of clauses and its number m of variables. The constructed graph
G has a node for every literal in φ, and because φ has k clauses, each with exactly 3 literals, G
has 3k nodes. We then add edges between each pair of nodes in G except for those between nodes
in the same triple nor between contradictory literals. So the number of edges in G is strictly less
than
(
3k
2
)
= 3k(3k − 1)/2 = O(k2), so the time to construct G is polynomial in m and k. Thus,
3SAT ≤P CLIQUE .
10. Recall that
ILP = { 〈A, b〉 | matrix A and vector b satisfy Ay ≤ b with y and integer vector }.
Show that ILP is NP-Complete by showing that ILP ∈ NP and 3SAT ≤P ILP . Explain your
reduction for the general case and not just for a specific example. Be sure to prove your reduction
works and that it requires polynomial time. Also, be sure to provide proofs of these results, and
don’t just cite a theorem.
Answer:
Step 1: show that ILP ∈ NP. To do this, we now give a polynomial-time verifier V using as a
certificate an integer vector c such that Ac ≤ b. Here is a verifier for ILP :
V = “On input 〈〈A, b〉, c〉:
1. Test whether c is a vector of all integers.
2. Test whether Ac ≤ b.
3. If both tests pass, accept ; otherwise, reject.”
13
If Ay ≤ b has m inequalities and n variables, we measure the size of the instance 〈A, b〉 as (m,n).
Stage 1 of V takes O(n) time, and Stage 2 takes O(mn) time. Hence, verifier V has O(mn) running
time, which is polynomial in size of problem.
Step 2: show 3SAT ≤m ILP . (We later show the reduction takes polynomial time.) To prove that
3SAT ≤m ILP , we need an algorithm that takes any instance φ of the 3SAT problem and converts
it into an instance of the ILP problem such that 〈φ〉 ∈ 3SAT if and only if the constructed integer
linear program has an integer solution. Suppose that φ has k clauses and m variables x1, x2, . . . , xm.
For the integer linear program, define 2m variables y1, y
′
1, y2, y
′
2, . . . , ym, y
′
m. Each yi corresponds
to xi, and each y
′
i corresponds to xi. For each i = 1, 2, . . . ,m, define the following inequality and
equality relations to be satisfied in the integer linear program:
0 ≤ yi ≤ 1, 0 ≤ y
′
i ≤ 1, yi + y
′
i = 1. (1)
If yi must be integer-valued and 0 ≤ yi ≤ 1, then yi can only take on the value 0 or 1. Similarly, y
′
i
can only take on the value 0 or 1. Hence, yi + y
′
i = 1 ensures exactly one of the pair (yi, y
′
i) is 1 and
the other is 0. This corresponds exactly to what xi and xi must satisfy.
Each clause in φ has the form (xi ∨ xj ∨ xk). For each such clause, create a corresponding inequality
yi + y
′
j + yk ≥ 1 (2)
to be included in the integer linear program. This ensures that each clause has at least one true
literal. By construction, φ is satisfiable if and only if the constructed integer linear program with m
sets of relations in display (1) and k inequations as in display (2) has an integer solution. Hence, we
have shown 3SAT ≤m ILP .
Step 3: show that the time to construct the integer linear program from a 3cnf-function φ is poly-
nomial in the size of 〈φ〉. We measure the size of 〈φ〉 in terms of the number m of variables and the
number k of clauses in φ. For each i = 1, 2, . . . ,m, display (1) comprises 6 inequalities:
• yi ≥ 0 (rewritten as −yi ≤ 0),
• yi ≤ 1,
• y′i ≥ 0 (rewritten as −y
′
i ≤ 0),
• y′i ≤ 1,
• yi + y
′
i ≤ 1, and
• yi + y
′
i ≥ 1 (rewritten as −yi − y
′
i ≤ −1),
where the last two together are equivalent to yi+y
′
i = 1. Thus, we have 6m inequalities corresponding
to display (1). The k clauses in φ leads to k more inequalities, each of the form in display (2). Thus,
the constructed integer linear program has 2m variables and 6m+ k linear inequalities, so the size of
the resulting integer linear program is polynomial in m and k. Hence, the reduction takes polynomial
time.
14
List of Theorems
Thm 1.A. The class of regular languages is closed under union.
Thm 1.B. The class of regular languages is closed under concatenation.
Thm 1.C. Every NFA has an equivalent DFA.
Thm 1.D. The class of regular languages is closed under Kleene-star.
Thm 1.E. (Kleene’s Theorem) Language A is regular iff A has a regular expression.
Thm 1.F. If A is finite language, then A is regular.
Thm 1.G. The class of regular languages is closed under intersection.
Thm 1.H. The class of regular languages is closed under complementation.
Thm 1.I. (Pumping lemma for regular languages) If A is regular language, then ∃ number p where, if
s ∈ A with |s| ≥ p, then ∃ strings x, y, z such that s = xyz and (1) xyiz ∈ A for each i ≥ 0, (2)
|y| > 0, and (3) |xy| ≤ p.
Thm 2.A. Every CFL can be described by a CFG G = (V,Σ, R, S) in Chomsky normal form, i.e., each
rule in G has one of two forms: A → BC or A → x, where A ∈ V , B,C ∈ V − {S}, x ∈ Σ, and we
also allow the rule S → ε.
Thm 2.B. If A is a regular language, then A is also a CFL.
Thm 2.C. A language is context free iff some PDA recognizes it.
Thm 2.D. (Pumping lemma for CFLs) For every CFL L, ∃ pumping length p such that ∀ strings s ∈ L
with |s| ≥ p, we can write s = uvxyz with (1) uvixyiz ∈ L ∀ i ≥ 0, (2) |vy| ≥ 1, (3) |vxy| ≤ p.
Thm 2.E. The class of CFLs is closed under union.
Thm 2.F. The class of CFLs is closed under concatenation.
Thm 2.G. The class of CFLs is closed under Kleene-star.
Thm 3.A. For every multi-tape TM M , there is a single-tape TM M ′ such that L(M) = L(M ′).
Thm 3.B. Every NTM has an equivalent deterministic TM.
Cor 3.C. Language L is Turing-recognizable iff an NTM recognizes it.
Thm 3.D. A language is enumerable iff some enumerator enumerates it.
Church-Turing Thesis. The informal notion of algorithm is the same as Turing machine algorithm.
Thm 4.A. ADFA = { 〈B,w〉 | B is a DFA that accepts string w } is Turing-decidable.
Thm 4.B. ANFA = { 〈B,w〉 | B is an NFA that accepts string w } is Turing-decidable.
Thm 4.C. AREX = { 〈R,w〉 | R is a regular expression that generates string w } is Turing-decidable.
Thm 4.D. EDFA = { 〈B〉 | B is a DFA with L(B) = ∅ } is Turing-decidable.
Thm 4.E. EQDFA = { 〈A,B〉 | A and B are DFAs with L(A) = L(B) } is Turing-decidable.
Thm 4.F. ACFG = { 〈G,w〉 | G is a CFG that generates string w } is Turing-decidable.
Thm 4.G. ECFG = { 〈G〉 | G is a CFG with L(G) = ∅ } is Turing-decidable.
Thm 4.H. Every CFL is Turing-decidable.
Thm 4.I. ATM = { 〈M,w〉 | M is a TM that accepts string w } is undecidable.
Thm 4.J. The set R of all real numbers is uncountable.
15
Cor 4.K. Some languages are not Turing-recognizable.
Thm 4.L. A language is decidable iff it is both Turing-recognizable and co-Turing-recognizable.
Cor 4.M. ATM is not Turing-recognizable.
Thm 5.A. HALTTM = { 〈M,w〉 | M is a TM that halts on w } is undecidable.
Thm 5.B. ETM = { 〈M〉 | M is a TM with L(M) = ∅ } is undecidable.
Thm 5.C. REGTM = { 〈M〉 | M is a TM and L(M) is regular } is undecidable.
Thm 5.D. EQTM = { 〈M1,M2〉 | M1, M2 are TMs with L(M1) = L(M2) } is undecidable.
Thm 5.E. (Rice’s Thm.) Let P be any subset of the class of Turing-recognizable languages such that
P 6= ∅ and P 6= ∅. Then LP = { 〈M〉 | L(M) ∈ P } is undecidable.
Thm 5.F. If A ≤m B and B is Turing-decidable, then A is Turing-decidable.
Cor 5.G. If A ≤m B and A is undecidable, then B is undecidable.
Thm 5.H. If A ≤m B and B is Turing-recognizable, then A is Turing-recognizable.
Cor 5.I. If A ≤m B and A is not Turing-recognizable, then B is not Turing-recognizable.
Thm 5.J. ETM = { 〈M〉 | M is a TM with L(M) = ∅ } is not Turing-recognizable.
Thm 5.K. EQTM = { 〈M1,M2〉 | M1,M2 are TMs with L(M1) = L(M2) } is neither Turing-recognizable
nor co-Turing-recognizable.
Thm 7.A. Let t(n) be a function with t(n) ≥ n. Then any t(n)-time multi-tape TM has an equivalent
O(t2(n))-time single-tape TM.
Thm 7.B. Let t(n) be a function with t(n) ≥ n. Then any t(n)-time NTM has an equivalent 2O(t(n))-time
deterministic 1-tape TM.
Thm 7.C. PATH ∈ P.
Thm 7.D. RELPRIME ∈ P.
Thm 7.E. Every CFL is in P.
Thm 7.F. A language is in NP iff it is decided by some nondeterministic polynomial-time TM.
Cor 7.G. NP =
⋃
k≥0NTIME(n
k)
Thm 7.H. CLIQUE ∈ NP.
Thm 7.I. SUBSET-SUM ∈ NP.
Thm 7.J. If A ≤P B and B ∈ P, then A ∈ P.
Thm 7.K. 3SAT is polynomial-time reducible to CLIQUE .
Thm 7.L. If there is an NP-Complete problem B and B ∈ P, then P = NP.
Thm 7.M. If B is NP-Complete and B ≤P C for C ∈ NP, then C is NP-Complete.
Thm 7.N. (Cook-Levin Thm.) SAT is NP-Complete.
Cor 7.O. 3SAT is NP-Complete.
Cor 7.P. CLIQUE is NP-Complete.
Thm 7.Q. ILP is NP-Complete.
16