CS 2030 : Theory of Computation : Final Exam Solutions

Subrahmanyam Kalyanasundaram
April 30, 2014

Some (most!) of these are solution sketches. For full credit, you need to provide all the details.
1. Consider the following language L1 .
L1 = {w {0, 1} | w contains at least three 0s and at least two 1s}.
(a) [4 marks] Show that L1 is regular.
There were several correct answers that I saw for this one. One can notice that the
language of strings with at least 3 zeros is regular, and the language with at least 2
ones is regular. The given language is the intersection of these two. It follows that L1
is regular because regular languages are closed under intersection. A few of you have
given the 12 state DFA that you can obtain when you try to construct the intersection
DFA. These are the simplest correct answers, although some of you have given correct
answers using regular expressions too.
(b) [6 marks] Show that any DFA recognising L1 must have at least 12 states. Provide a
minimal DFA for L1 .
The correct answer is using Myhill-Nerode theorem. Consider the strings 0i 1j , where
0 i 3 and 0 j 2). One can show that these 12 strings are distinguishable. As a
consequence, the index of L1 is at least 12. And the index is exactly 12, because we can
build a 12 state DFA. This is the DFA that we obtain when we build the intersection DFA
for the above part. One or two of you have given the argument without using MyhillNerode, but instead building a 12-state DFA and showing that all states are necessary.
2. (a) [5 marks] If A is a regular language, then show that the language PREFIX (A) (defined
below) is regular as well.
PREFIX (A) = {w| y such that wy A}.
We need a DFA that accepts any string that is a prefix of a string in the language A.
Since A is regular, we will modify the DFA of A to get a DFA for PREFIX (A). Consider
any state q of the DFA M that recognises A. If the state q has a path that can lead to
an accepting state, we make q an accepting state of the modified DFA M 0 that accepts
PREFIX (A). The logic is straightforward. Any string that is a prefix of a string in A
must end in a state which has a path to an accepting state of M .
One comment is that for showing that PREFIX (A) is regular, it is enough to show that
there is a DFA for PREFIX (A). We do not need to provide an algorithm for constructing
1

the DFA. Proof of existence is enough. Another comment is that several of you have said
that PREFIX (A) is regular because regular languages are closed under concatenation.
This is not correct. Some of you have used that if A is a regular language such that
A = A1 A2 , it necessarily implies that A1 and A2 are regular. This is not correct too.
You can construct counter examples for this.
(b) [5 marks] Show that the following language L2 is not regular.
L2 = {w {0, 1} | the number of 0s and 1s in w differ (in either direction) by at most 2014}.
We can use pumping lemma to show this. If L2 is regular, then it has to satisfy pumping
lemma. Let p be the pumping length. Consider the string 0p+2014 1p L2 . This string
can be pumped because it is longer than p. So it can be broken into xyz such that
|xy| p, |y| > 0 and xy i z L2 for all i 0. Since |xy| p, y has to necessarily be
of the form 0k where k > 0. If we take xy 2 z = 0p+k+2014 1p , we get a string that is not
in L2 and hence 0p+2014 1p cannot be pumped. This means L2 does not satisfy pumping
lemma and hence is not regular.
I found that several of you still do not apply the pumping lemma in the correct manner.
It seems that a large part of students in the class still are not clear that, (i) you use
pumping lemma as a necessary and not a sufficient condition, (ii) you can choose the
string, (iii) you have to show that it cannot be pumped for any possible legal splits.
3. Are the languages defined below context-free? Provide proofs for your answers.
(a) [5 marks] L3 = {an bn+m cm dn | m, n 0}.
L3 is not context-free. One way is to use pumping lemma. You can show that ap bp dp
cannot be pumped. An easier approach is to note that L3 a b d has to be a contextfree language if L3 is context-free (refer exercises). But L3 a b d = {an bn dn | n 0}
which we have seen in class to be not context-free.
(b) [5 marks] L4 = {an bm cm dn | m, n 0}.
L4 is a CFL. You can build a PDA that recognises L4 . It is also easy to see that the
following CFG generates L4 .
S aSd|T
bT c|

4. (a) [6 marks] Show that the following language L5 is not Turing-recognisable.

L5 = {hM i| M is a TM and L(M ) is finite}.
We can construct a reduction from ATM to L5 . This would imply that ATM m L5 . Since
ATM is not Turing recognisable, this would imply that L5 is also not Turing recognisable.
The reduction is the following: Given hM, wi, we construct M1 . The TM M1 on any
input x, simulates M on w and accepts x if M accepts w. So L(M1 ) = if M accepts
w and L(M1 ) = if M does not accept w. That is hM1 i 6 L5 hM, wi ATM .

(b) [4 marks] Is the following language L6 decidable, Turing-recognisable, co-Turing recognisable? Provide the most accurate answer with proof.
L6 = {hM i| M is a TM and L(M ) is countable}.
L6 is decidable. One simply has to check if the given encoding is proper. We have seen
that for any finite alphabet , the set is countable. Any language is a subset of
and is hence countable too. So given any Turing machine M , L(M ) is countable. So L6
is simply the set of all Turing machines.
5. [10 marks] Consider the following language L7 .
L7 = {w | either w = 0x for some x ATM , or w = 1y for some y ATM }
Show that neither L7 nor L7 is Turing recognizable.
To show that L7 is neither Turing recognisable nor co-Turing recognisable, we will show that
ATM m L7 and ATM m L7 . ATM m L7 implies that L7 is not Turing recognisable.
ATM m L7 implies that ATM m L7 which implies that L7 is not Turing recognisable.
Both reductions are extremely simple. We have x ATM 0x L7 and y ATM
1y L7 .
6. (a) [8 marks] Let G be an undirected graph with n vertices. Assume that there is an oracle
that takes input hG, ki and outputs YES if G contains a k-clique, and NO if G does
not. Show that you can make O(n) calls to this oracle to find out the largest clique in
the graph (Not just the size of the largest clique, but the clique itself). Conclude that if
P = NP, there exists a polynomial time algorithm to determine the largest clique of the
graph.
We could call the oracle n times, hG, ni, hG, n 1i, . . . , hG, 2i and hG, 1i to find out the
size of the largest clique of the graph G. Suppose the size of the largest clique is p. Then
we can query the oracle hG\{v1 }, pi. If the oracle answers NO, then it means that the
vertex v1 is present in the largest clique. The largest clique includes v1 and a clique of
size p 1 from G\{v1 }. If oracle answers YES, then it means that there is a clique of
size p in G\{v1 }.
Depending on whether v1 is present or not in the largest clique, we query the oracle
with hG\{v1 , v2 }, p 1i or hG\{v1 , v2 }, pi to find out whether v2 is present in the largest
clique. We continue for all the n vertices of G. We make at most 2n calls.
If P = NP, the oracle could be replaced by a polynomial time algorithm. This is because
the decision problem answered by the oracle is in NP and P = NP would imply that there
is a polynomial time algorithm which could replace the oracle. So the entire algorithm
would be polynomial time algorithm without any help of any oracle.
Several of you have used nondeterminism in your answer. You are not supposed to use
nondeterminism. As you see above, you can get an answer without using nondeterminism.
(b) [2 marks] Show that the above part can be done by using n + log2 n calls to the oracle.
We used 2n calls to the oracle in the first part. We could replace the initial n calls with
log2 n calls. We can use binary search to determine the size of the largest clique of G.
3

7. Consider the following two languages.

SUBSET-SUM = {hS, ti | S = {x1 , x2 , . . . , xn } and I {1, 2, . . . , n} such that

xi = t}.

iI

COMPOSITE = {hyi | y is a composite integer}.

SUBSET-SUM is NP-complete and COMPOSITE is in NP. Using these two facts, state
whether each of the following statements is True or False, along with a short explanation.
(a) [2 marks] SUBSET-SUM P COMPOSITE.
False. NP-completeness of SUBSET-SUM means that COMPOSITE P SUBSET-SUM
and not the other way round.

(b) [2 marks] If there is an O(n t) algorithm for SUBSET-SUM, then P = NP.

False. A polynomial time algorithm for SUBSET-SUM
would mean that P = NP,

since SUBSET-SUM is NP-complete. An O(n t) algorithm is not a polynomial time

algorithm because the description of t requires only O(log n) length. So we cannot infer
that P = NP.
(c) [2 marks] If there is an O(n3 log t) algorithm for SUBSET-SUM, then there is a polynomial time algorithm for COMPOSITE.
True. An O(n3 log t) algorithm is a polynomial time algorithm for SUBSET-SUM. This
means that P = NP. Since COMPOSITE is in NP, this implies that there is a polynomial
time algorithm for COMPOSITE.
(d) [2 marks] If there is an O(log y) algorithm for COMPOSITE, then P = NP.
False. An O(log y) algorithm for COMPOSITE is a polynomial time algorithm, but
since COMPOSITE is not given to be an NP-complete problem, we cannot make any
inference about P being equal to NP
(e) [2 marks] If P 6= NP, then no problem in NP can be solved in polynomial time.
False. Even if P 6= NP, P is still a subset of NP. So problems which are in P could be
solved in polynomial time.
Vague answers and answers without reasons have not received any credit.
8. [10 marks] An instance of SET-COVER is given by a ground set U = {x1 , x2 , . . . , xn }, a
collection S = {S1 , . . . Sm } of m subsets Si U , and an integer k. The question is, can you
select a collection of at most k of these subsets such that taken together, they cover all of
U ? More formally:
SET-COVER = {hU, S, ki | C S, |C| = k such that Si C Si = U }
Show that SET-COVER is NP-complete.
An nondeterministic TM can guess the collection of k sets that cover U . It can verified in
deterministic polynomial time that the guessed collection indeed covers U . This shows that
SET-COVER is in NP.
You can show that SET-COVER is NP-hard by reducing VERTEX-COVER to it. Given a
VERTEX-COVER instance hG, ki, you can construct a corresponding SET-COVER instance
4

hU, S, ki. The universe set is U is the set of edges of G. The collection of sets S1 , S2 , . . .
correspond to the edges adjacent to each of the vertices v1 , v2 , . . . in G. That is, the set Si is
the set of edges covered by the vertex vi . The correctness is straightforward.
9. [10 marks] Show that 2-SAT is in NL.
2-SAT = {hi | is a satisfiable 2-cnf formula}.
One approach would be to guess and verify if an assignment is satisfiable. But guessing an
assignment requires linear space in the number of variables. So we cannot use this approach.
However, we have seen that NL = co-NL and it is enough to show that 2-SAT is in co-NL. We
saw that 2-SAT is in P. Given a 2-cnf formula , we can construct a directed graph G. The
graph has 2n vertices, where n is the number of variables of . There is one vertex for each
literal of x1 , x1 , . . . , xn , xn . For a clause (p q), there are two directed edges (p, q) and
(q, p). We saw in the homeworks that is unsatisfiable if and only if there exists a variable
xi such that there exists a directed path from xi to xi and one from xi to xi .
To check that 2-SAT NL, it is enough to guess a variable xi and the NL machine can verify
that there are directed paths from xi to xi and one from xi to xi . This shows that 2-SAT is
in co-NL and hence in NL.
10. (a) [2 marks] Is the following fully quantified formula TQBF ? Explain your answer.
= x1 x2 x3 [(x1 x3 ) (x2 x3 ) (x1 x2 )] .
The given formula is not in TQBF. This can be seen as follows. If we pick x1 to be
TRUE, the adversary can negate the formula by picking x2 to be TRUE and so the third
clause is not satisfied. If we pick x1 to FALSE, the adversary picks x2 to be FALSE. To
satisfy the first clause, now we need to pick x3 to be TRUE. But to satisfy the second
clause, we need to set x3 to FALSE. So there is no choice of x3 that satisfies the formula.
(b) [3 marks] Show that TQBF NP = NP = PSPACE.
We have seen in class that NP PSPACE. We use polynomial time reductions for
PSPACE-completeness. For any language A PSPACE, we have that A P TQBF
because of the PSPACE-completeness of TQBF. If TQBF NP, then it follows that for
any A PSPACE, A NP. So PSPACE NP, giving us equality of the two classes.
(c) [3 marks] When we defined NL-completeness, we defined a class of reductions called
logspace reductions. If we had used polynomial time reductions to define NL-completeness,
what would have been the issue?
We have seen that NL P. So polynomial time reductions are more powerful than
the NL complexity class. If we allowed polynomial time reductions in the definition of
NL-completeness, then any language in NL could be solved in polynomial time. Any
language in NL could then be reduced (in polynomial time) to any non-trivial language
(one which is not or ) in NL. The NL-completeness would be meaningless defined
in this manner.
(d) [1 marks] Does Savitchs theorem imply that NSPACE(log n) DSPACE(log n)? Why
or why not?
Savitchs theorem states that NSPACE(f (n)) DSPACE((f (n))2 ) when f (n) log n.
So it does not imply the given statement. It implies that NSPACE(log n) DSPACE(log2 n).
5

(e) [1 marks] Does Savitchs theorem imply that NSPACE(n3 ) DSPACE(n6 )? Why or
why not?
Yes, since n6 = (n3 )2 .