Question

2. (10 points) Consider the following computational problems:

EQDF A = {hA, Bi | A and B are DFAs and L(A) = L(B)}

SUBDF A = {hA, Bi | A and B are DFAs and L(A) ⊆ L(B)}

DISJDF A = {hA, Bi | A and B are DFAs and L(A) ∩ L(B) = ∅}.

Prove that SUBDF A and DISJDF A are each Turing-decidable.

You may (and should) use high-level descriptions of any Turing machines you define. Make sure to provide both a machine definition and a proof of correctness.

2. (10 points) Consider the following computational problems: EQDFA = {(A,B) | A and B are DFAs and L(A) = L(B)) SUBDFA = {(A,B) | A and B are DFAs and L(A) L(B)) DISJDFA = {(A,B) | A and B are DFAs and L(A) L(B) = } Prove that SUBDFA and DISJDFA are each Turing-decidable. You may (and should) use high-level descriptions of any Turing machines you define. Make sure to provide both a machine definition and a proof of correctness.

Answer 1

Solution for $SUB_{DFA}$ is Turing decidable or not.

Given $\item[] $SUB_{DFA} = \{ \langle A, B \rangle \st \text{$A$ and $B$ are DFAs and $L(A) \subseteq L(B)$} \}$$

Let $X$ and $Y$ be two sets. Then $X \subseteq Y iff X \cap \overline{Y} = \Phi$

Thus based on the above Idea:

Define TM $M_{1}$ by : $M_{1}$ = "On Input $\left \langle A, B \right \rangle$ where $A, B$$DFA$'s

1. Construct a new $DFA$$D$ from $A, B$ such that $DFA$   $D$ is intersection of $A$ and $\overline{B}$ as we know that intersection and complement of DFA is decidable. Thus
   $L(D) = L(A) \cap \overline{L(B)}$
2. We know that $E_{DFA}$ is decidable. ie Empty DFA is Turing decidable.
   Thus TM $M_{1}$ accepts if $L(D)$ is empty and rejects otherwise.

Solution (b) To prove $DISJ_{DFA}$ is Turing decidable.
$$DISJ_{DFA} = \{ \langle A, B \rangle \st \text{$A$ and $B$ are DFAs and $L(A) \cap L(B) = \emptyset$} \} $.$

From Demorgan's law we know the fact that if $X$ and $Y$ are two sets

Then $X$$\cap$$Y$ = $\overline{\overline{X}\cup \overline{Y}}$ . And we also know that union and complement of DFA are decidable thus the intersection is also decidable.

Based on Above Idea:

Define TM $M_{2}$ by : $M_{2}$ = "On Input $\left \langle A, B \right \rangle$ where $A, B$$DFA$'s

1. Construct a new $DFA$$D$ from $A, B$ such that $DFA$   $D$ is intersection of $A$ and $B$ as we know that intersection of two DFAs is decidable. Thus
   $L(D) = L(A) \cap L(B)$
2. We know that $E_{DFA}$ is decidable. ie Empty DFA is Turing decidable.
   Thus TM $M_{2}$ accepts if $L(D)$ is empty and rejects otherwise.

Proof of correctness is just to tell that M1 and M2 is decider and the L(M1) and L(M2) are indeed equivalent to SUB_DFA and DISJ_DFA.