1. Short answers:
Practice Problems for Final Exam: Solutions CS 341: Foundations of Computer Science II Prof. Marvin K. Nakayama
(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̸∈T}
Complement: S={x∈Ω|x̸∈S}=Ω−S,whereΩistheuniverseofallelementsunder 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 ̸∈ 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 ̸∈ 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 thatw∈Aifandonlyiff(w)∈B. Thus,ifA≤m B,wecandetermineifastringw belongs to A by checking if f(w) belongs to 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 s u c h t h a t w ∈ A i f a n d o n l y i f 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.
Σ∗1
A
NP
Σ∗2
B
A2
2
A3
B
A4
A5
A1
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.
NP
A3
A4
A2
B
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,whereQisthesetofstatesandΣisthealphabet.
• NFA, δ : Q × Σε → P(Q), where Σε = Σ ∪ {ε} and P(Q) is the power set of Q
• PDA,δ:Q×Σε×Γε →P(Q×Γε),whereΓisthestackalphabetandΓε =Γ∪{ε}.
• 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 ̸= 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.
⟨ M , w ⟩ −→
✟✯✟ accept, if ⟨M, w⟩ ∈ ATM
✟ ✟
3
❍❍
❍❥❍ reject, if ⟨M, w⟩ ̸∈ A
TM
A5
A1
C
H
Define another TM D using H as a subroutine.
Type REG. Type CFL. Type DEC.
It is regular.
It is context-free, but not regular.
It is Turing-decidable, but not context-free.
⟨M⟩ −→
✟✟✯ accept ✟
✟
❍ ❍
❍❍❥ reject
D
⟨M,⟨M⟩⟩ −→
✟✟✯ accept ❍❍
H
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⟩?
⟨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⟩, whereMisaTMandwisastring. IfTMMacceptsstringw,then⟨M,w⟩∈ATM andH accepts input ⟨M,w⟩. If TM M does not accept string w, then ⟨M,w⟩ ̸∈ 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 = “Oninput⟨M⟩,whereM isaTM: 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 = “Oninput⟨M,w⟩,whereM isaTMandwisastring: 1.RunM onw.
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:
For each of the following languages, specify which type it is. Also, follow these instructions: 4
✟❍
✟ ❍✟ ❍❍ ✟❍
✟ ❍❍❥ reject ✟✟
D
⟨D,⟨D⟩⟩ −→
✟✟✯ accept ❍❍ ✟❍
H
✟ ❍✟
❍❍ ✟❍ ✟
❍❍❥ reject ✟✟
• 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)andthelengthofwisdivisibleby4},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 variableS,andrulesR={S→00S00|01S10|10S01|11S11|ε}. APDAforAisasfollows:
q1 ε, ε → $ q2 0, ε→0
1, ε→1
q3
ε, ε → ε
q4
q5
ε, $ → ε q6 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,wherej+k+m=pbecauses=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) ̸= xyyz, which means xyyz ̸∈ 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 =uvxyzsatisfyinguvixyiz∈Bforalli≥0,|vy|≥1,and|vxy|≤p. Wenow consider all of the possible choices for v and y:
•Supposestringsvandyareuniform(e.g.,v=bj forsomej≥0,andy=ak forsome k≥0). Then|vy|≥1impliesthatv̸=εory̸=ε(orboth),souv2xy2zwon’thave the correct number of b’s at the beginning, a’s in the middle, and b’s at the end. Hence, uv2xy2z ̸∈ B.
• Now suppose strings v and y are not both uniform. Then uv2xy2z will not have the form b···ba···ab···b. Hence, uv2xy2z ̸∈ 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) mod4=1},whereΣ={a,b}andna(w)isthenumberofa’sinstring w. For example, na(babaabb) = 3. Also, recall j mod k returns the remainder after dividing j byk,e.g.,3 mod4=3,and9 mod4=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
bb
q1 a q2
a q4 a q3
bb
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
ab
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},
a
S as the starting variable, and rules R:
A PDA for D is below:
b, ε → b
q1 ε, ε → $ q2
ε, ε → ε
S → XY
X → bXa|ε
Y → bYc|ε
a, b → ε b, ε → b
q3 ε, $ → $ q4
ε, ε → ε
c, b → ε
q5 ε, $ → ε q6
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 transitionfunctionδ:Q×Σε×Γε →P(Q×Γε)isdefinedby
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 splits=xyzsatisfying(1)xyiz∈Dforalli≥0,(2)|y|>0,and(3)|xy|≤p. Becauseallof 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,wherej+k+m=pbecauses=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
becausej+k+m=p. Alsok>0,soxyyz̸∈D,whichcontradicts(1). Therefore,Disa
nonregular language.
4. Each of the languages below in parts (a), (b), (c), (d) is of one of the following types:
Type DEC. Type TMR. Type NTR.
It is Turing-decidable.
It is Turing-recognizable, but not decidable. 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⟩ ̸∈ 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⟩ ̸∈ ATM, so M accepts w), then L(M1) = ∅ and L(M2) = Σ∗, which are not the same, implying that f(⟨M,w⟩) = ⟨M1,M2⟩ ̸∈ 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 = “Oninput⟨M,w⟩,whereM isaTMandwisastring: 1.RunM onw.
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 = “Oninput⟨M,w⟩,whereM isaTMandwisastring: 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⟩ ̸∈ 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 = {akbk}.]
Answer: The answer is NO. For each k ≥ 1, let Lk = {akbk}, 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 ={akbk |k≥1},whichweknowisnotregular(seeendofChapter1).
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.
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|YZ
Z → ZY|a
Y → b|ZZ|YY
Use the CYK (dynamic programming) algorithm to fill in the following table to determine if G generates the string babba. Does G generate babba?
Operation
Regular languages
CFLs
Decidable languages
Turing-recognizable 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)
11
12345 1
2 3 4 5
babba 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 k2 = 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
Y
S
S
S
Y
S,Z
Z
Z
Y
Y
Y
S
Y
S
S,Z
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 = 3k(3k − 1)/2 = O(k2), so the time to construct G is polynomial in m and k. Thus, 2
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, y1′ , y2, y2′ , . . . , ym, ym′ . Each yi corresponds to xi, and each yi′ 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≤yi′ ≤1, yi +yi′ =1. (1)
If yi must be integer-valued and 0 ≤ yi ≤ 1, then yi ca