Name: Rollno:

CSE340: Theory of Computation (Final Exam)

18th November, 2017

Total Number of Pages: 6 Total Points 100

Instructions Question Points Score

1. Read these instructions carefully. 1 10
2. Write you name and roll number on all the 2 12
pages.
3 6
3. Cheating or resorting to unfair means will be
severely penalized. 4 6

S
4. Do not exchange question books or change the 5 7
seat after obtaining question paper. 6 10

N
5. Superfluous and irrelevant writing will result in 7 14
negative marking.
8 6
6. Using pens (blue/black ink) and not pencils.
Do not use red pens for answering. 9 18
IO
10 11
Helpful hints
Total: 100
1. It is advisable to solve a problem first before
writing down the solution.
2. The questions are not arranged according to the Useful Information
T

increasing order of difficulty.

1. TR = {L | L is Turing recognizable}
3. For each question, you are given more space
than what is needed for writing your solutions. 2. coTR = {L | L ∈ TR}
LU

Question 1. (10 points) For each of the following languages encircle the smallest class in which the problem
is known to be contained.
(2 marks for correct answer, 0.5 mark for leaving the question blank and 0 mark for incorrect answer)
(a) {ai bj ci | i, j ≥ 0}
A. Regular B. Context-free C. Decidable D. Undecidable
SO

∗
(b) {hM i | M is a TM and L(M ) = Σ }
A. Decidable B. TR C. coTR D. Neither in TR nor in coTR
(c) {hM i | M is a TM and L(M ) ∈ NP}
A. P B. NP C. Decidable D. Undecidable
(d) {hG, ki | G has a clique of size k}
A. P B. EXP C. PSPACE D. NEXP

Page 1 of 6
Name: Rollno:
(e) {hφi | φ is a Boolean formula that evaluates to true on every truth assignment}
A. P B. NP C. NP-complete D. NEXP
Question 2. (12 points) For each of the following statements, state whether it is True, False or Open based
on our current knowledge.
(2 marks for correct answer, 0.5 mark for leaving the question blank and 0 mark for incorrect answer)
(a) NL ⊆ P True
10
(b) P ⊆ TIME(n ) False
(c) Clique ≤p Clique Open
(d) TR = coTR False
(e) PSPACE ⊆ EXP True
(f) SAT ∈ L Open
Question 3. Consider the following property of languages. For all L ⊆ Σ∗ ,

1 if ∃ a TM M with an even no. of states such that L = L(M )
P (L) =
0 otherwise

(a) (2 points) P is a non-trivial property of languages of TMs (True or False). False

(b) (2 points) Give reason for your answer in part (a).

Solution: For every language L such that L = L(M ) for some TM M , there exists a TM with
an even no. of states (if the no. of states in M is odd, add a dummy state).

(c) (2 points) Is the language L = {hM i | M has an even no. of states} decidable? Give reason for
your answer.

Solution: Yes. Just count the no. of states in M and answer accordingly.

Question 4. (6 points) Let p and q be two positive integers. Give a CFG for the following language, having
only one variable (say S)
L = {ai bj | i, j ≥ 0, pi = qj}.

Solution: q p
S −→ a gcd(p,q) Sb gcd(p,q) | 
So if you assume p and q are coprime the solution is

S −→ aq Sbp | 

Question 5. Consider the language

L = {hM1 , M2 i | M1 , M2 are two TMs and L(M1 ) ⊆ L(M2 )}.

(a) (1 point) Is L decidable? No

(b) (6 points) Prove your answer.

Page 2 of 6
Name: Rollno:

Solution: Consider the undecidable language

ETM = {hM i | M is a TM and L(M ) = ∅}.

Claim 1. ETM ≤m L.
We will construct a computable function f that takes as input hM i and produces an output
hM1 , M2 i such that L(M ) = ∅ ⇐⇒ L(M1 ) ⊆ L(M2 ).

The reduction function f

Input: hM i

1. Set M1 := M .
2. Set M2 to be a TM that rejects all strings (L(M2 ) = ∅).

Output: hM1 , M2 i
Note that L(M2 ) = Σ∗ .

Proof of correctness

Now,

L(M ) = ∅ ⇐⇒ L(M1 ) = ∅ ⇐⇒ L(M1 ) ∩ L(M2 ) = ∅ ⇐⇒ L(M1 ) ⊆ L(M2 )

Therefore, ETM ≤m L. This proves that L is undecidable.

Question 6. Recall that

ETM = {hM i | L(M ) = ∅}.
Consider two languages L1 and L2 defined as follows:

L1 = {hN i | N is a TM and L(N ) = ETM }

L2 = {hN i | N is a TM and L(N ) = ETM }.

One of the above two languages is decidable and the other is not.
(a) (2 points) The language L1 is decidable.
(b) (3 points) Why is the language in part (a) decidable?

Solution: We have show in class that ATM is undecidable but in TR and ATM ≤m ETM .
Therefore ETM is in coTR and not in TR. Hence there does not exist any TM M such that
L(M ) = ETM . Hence L1 is empty set and thus decidable.

(c) (3 points) Why is the other language undecidable? (You may use Rice’s Theorem for this part)

Solution: Given a TM M , we can nondeterministically guess a string x and verify whether M

accepts x. If L(M ) 6= ∅ then there exists a string for which this is true. Hence ETM is in TR.
Therefore there exists a TM N1 such that L(N1 ) = ETM . Also there exists a TM N2 such that
L(N2 ) 6= ETM (say N2 is the TM that rejects all strings). Therefore by Rice’s Theorem L2 is
undecidable.

Page 3 of 6
Name: Rollno:
(d) (2 points) What can we say about L1 and L2 if we replace ETM with the language FIN? (Recall
that FIN = {hM i | L(M ) is finite}.)
- L1 is decidable .
- L2 is decidable .
Question 7. (a) (6 points) Show that for every k ≥ 0, NTIME(nk ) ( PSPACE.

Solution: Let k ≥ 0. Then,

NTIME(nk ) ⊆ NSPACE(nk )
⊆ SPACE(n2k ) by Savitch’s Theorem
2k+1
( SPACE(n ) by Space Hierarchy Theorem
⊆ PSPACE.

(b) (4 points) Since NP = ∪k≥0 NTIME(nk ), does this show that NP ( PSPACE? Why?

Solution: No. Because part (a) shows that for every k there is a problem in PSPACE that is
not in NTIME(nk ), but the problem can very well be in NTIME(nl ) for some l > k. However
to show that NP ( PSPACE one needs to show that there is a problem in PSPACE that is not
NTIME(nk ) for every k.

NSPACE(logk n) = SPACE(logk n).

S S
(c) (4 points) Show that k≥0 k≥0

SPACE(logk n) ⊆ NSPACE(logk n).

S S
Solution: By definition, k≥0 k≥0
k
S L ∈ NSPACE(log
Let for some k. Then by Savitch’s Theorem, L ∈ SPACE(log2k n). Hence
n) S
k k
k≥0 NSPACE(log n) ⊆ k≥0 SPACE(log n) as well.

Question 8. (6 points) Design an NFA with at most six states that accepts the following language

L = {0n+3k 1n | n ≥ 0, k ∈ Z}.

Solution: Observe that, we can rephrase L as set of strings of the form 0i 1j such that i and j leave
the same remainder modulo 3.
Here is an NFA for L.

Page 4 of 6
Name: Rollno:

1 1
start

0 0
0




Question 9. Let Σ be some fixed alphabet. For any string w ∈ Σ∗ , let wR denote the reverse of w. Let A
be a regular language. Consider the following two languages

L1 = {wwR | w ∈ A}
L2 = {w | wwR ∈ A}.

One of the above two languages is necessarily regular, and one is not. Which is which? Give a proof and
a counterexample.
(a) (1 point) L2 is regular.
(b) (1 point) L1 is not regular.
(c) (8 points) Prove that the language in part (a) is regular.

Solution: Let D = (Q, Σ, δ, q0 , F ) be a DFA for A. We will construct an NFA N for L2 that
will simultaneously simulate the input string w from the starting state in forward direction, and
from the accepting states in reverse direction. If at the end of reading w, both the simulations
reach the same state we accept otherwise reject.
Define N = (Q2 ∪ {s}, Σ, δN , s, FN ).
From the start state s of N , we add transitions of the form

δN (s, ) = {(q0 , f ) | f ∈ F }.

The other transitions of N are defined as

δN ((p1 , q1 ), a) = {(p2 , q2 ) | δ(p1 , a) = p2 and δ(q2 , a) = q1 }.

The set of accepting states of N are

FN = {(p, p) | p ∈ Q}.

Then L2 = L(N ).

(d) (8 points) Prove that the language in part (b) is not regular by giving a suitable counter example
and showing why it is not regular.

Page 5 of 6
Name: Rollno:

Solution: Let A = {0 + 1}∗ which is clearly regular. Then L1 = {wwR | w ∈ {0 + 1}∗ }. We

prove L1 is not regular using the Pumping Lemma for regular languages.
Given n ≥ 1, pick w = 0n 110n which is a string in L1 . Now for any partition of w = xyz such
that |xy| ≤ n and |y| > 0, y will be of the form 0i , where 0 < i ≤ n. Therefore the string
xy 0 z = 0n−i 110n and is clearly not in L1 . Therefore L1 is not regular.

Question 10. A walk in a graph G = (V, E) is a sequence of vertices P = (v0 , v1 , . . . , vk ) such that
(vi−1 , vi ) ∈ E for 1 ≤ i ≤ k. Given an edge weight function w : E −→ Z, weight of the above
Pk
walk P , w(P ) = i=1 w(vi−1 , vi ).
TSP = {hG, w, ki |G is a directed graph, w is an edge weight function,
∃ a walk P in G s.t. w(P ) ≤ k and P visits every vertex at least once}
In this question we will show that TSP is NP-complete.
(a) (3 points) Show that TSP ∈ NP.

Solution: Certificate: A sequence of vertices v1 , . . . , vm .

Verifier’s Algorithm
Input: hG, w, k, v1 , . . . , vm i

1. Check if (vi , vi+1 ) is an edge for all 1 ≤ i ≤ m − 1. If not then REJECT.

Pm−1
2. Check if i=1 w(vi , vi+1 ) ≤ k. If not then REJECT.
3. Check if v1 , . . . , vm covers all the vertices in G. If so then ACCEPT else REJECT.

(b) (1 point) Choosing a known NP-complete problem: HamPath

(c) (4 points) Give the reduction

Solution: Let hG = (V, E)i be an instance of HamPath. We will construct an instance of TSP,
hG0 = (V 0 , E 0 ), w, ki as defined below:

V0 =V
E0 = E
w(e) = 1 ∀e ∈ E 0
k = |V | − 1

(d) (1 point) Time complexity of the reduction

Solution: The construction of hG0 , w, ki can be done in linear time in the size of G.

(e) (2 points) Proof of correctness of the reduction.

Solution: If G has a Hamiltonian path P then w(P ) = |V | − 1 hence G0 has a walk of weight
at most k that visits all vertices (the path P itself).
If G0 has a walk of weight at most k that visits all vertices then the walk must be a path since
k = |V | − 1. Hence G has a Hamiltonian path.

Page 6 of 6