CS4123 Theory of Computation. B2002
Solutions - EXAM 2 December 12, 2002.

By Prof. Carolina Ruiz.   Department of Computer Science.   Worcester Polytechnic Institute


Instructions


Problem 1 - Decidability (25 points)

Let Sigma be an alphabet. Show that the following language is decidable by constructing a Turing machine that decides it:
ALLDFA = {<D> | D is a DFA and L(D) = Sigma*}
In other words, construct a Turing machine that decides the following problem:

Solution 1.

Let's construct a Turing machine M to decide the ALLDFA problem.

M =" On input x,

  1. Check that x codifies a DFA. If so, denote the DFA by A = (Q,Sigma,delta,q_0,F). If x doesn't codify a DFA, reject x.
  2. Construct the following DFA AC: AC = (Q,Sigma,delta,q_0,Q-F).
  3. Run <AC> on the Turing machine T that decides the EDFA problem (see Theorem 4.4).
  4. If T accepts <AC>, then accept x.
  5. If T rejects <AC>, then reject x."
It is easy to see that L(A) and L(AC) are the complement of each other with respect to Sigma*. That is, L(A) = Sigma* - L(AC).
Hence, L(A) = Sigma* iff L(AC) = empty. Determining if L(AC) is empty is decidable due to Theorem 4.5, and so determining if L(A) = Sigma* is decidable as well.

Alternative Solution 2.

Let's construct a Turing machine M to decide the ALLDFA problem.

M =" On input x,

  1. Check that x codifies a DFA. If so, denote the DFA by A = (Q,Sigma,delta,q_0,F). If x doesn't codify a DFA, reject x.
  2. Construct the DFA S = ({q},Sigma,delta,q,{q}), where delta(q,a) = q, for all a in Sigma.
  3. Run the pair <A,S> on the Turing machine F that decides the EQDFA problem (see Theorem 4.5).
  4. If F accepts <A,S>, then accept x.
  5. If F rejects <A,S>, then reject x."
Clearly S accepts every word in Sigma* and so L(S) = Sigma*. Given a DFA A, A belongs to ALLdfa iff L(A) = L(S). By Theorem 4.5 (EQUIVdfa is decidable), the condition L(A)=L(S) is decidable, and so determining if A belongs to ALLdfa is decidable too.

Problem 2 - Semi-Decidability (25 points)

Show that the acceptance problem for Turing machines
ATM = {<M,w> | M is a TM and M accepts input w} is semi-decidable.

In other words, construct a Turing machine that semi-decides the following problem:

Solution
Let's construct a semi-decider U for ATM:

U = "On input x,

  1. Check that x codifies a Turing machine M and a string w. If not, reject x.
  2. Run the machine M on input w.
    1. If M accepts w, then accept x = < M,w >.
    2. If M rejects w, then reject x = < M,w >.
    3. [note that if M loops on w, then U will loop on x.]"
U semi-decides ATM, because U accepts < M,w > if and only if M accepts w.

Problem 3 - Undecidability (25 points)

Show that the equivalence problem for Turing machines
EQTM = {<M1,M2> | M1 and M2 are TMs and L(M1) = L(M2)} is undecidable.

In other words, show that there is NO Turing machine that decides the following problem:

Solution
See the proof of Theorem 5.4 (page 176) in your textbook. [Of course your solution in the exam cannot be just stating that a theorem in the book proves this. You need to prove it yourself.

Problem 4 - NP-Completeness (25 points)

Consider the Traveling Salesman problem: