Question

Given two DFAs, A and B, show that you can construct a DFA C such that L(C) = ∅ if and only if L(A) ⊆ L(B). Prove that your construction works by proving the if and only if statement.

Answer 1

- The language L1 is decidable. A decider for L1 would work as follows:
”On input hA;Bi:
1. Construct a DFA C such that L(C) = L(A) \ L(B).
2. Test whether L(C) = ; or not. If yes then accept else reject.”
The step 1. is surely algorithmic using the classical product construction (covered in the formal
automata course). Step 2. is also algorithmic because we already discussed that the emptiness
problem EDFA is decidable for DFA.
-The language L2 is decidable. A decider M2 for L2 would on the input hMi do the following. It
would inspect the description ofM present on the first tape and count the total number control states
in M. Should the number be greater than 5 then M2 would accept, otherwise M2 would reject. This
algorithm will surely terminate and hence we have a decider M2 for L2.
- The language L3 is decidable. Consider the following Turing machine M3 deciding L3:

M3 = ”On input hM;wi:
1. i:=1;
2. Simulate one step of M on w.
3. If M accepted w then M3 accepts.
If M rejected w then M3 rejects.
If i >= 1000 then M3 rejects.
4. Else i:=i+1; goto step 2.”
Clearly the machine M3 is decider as the main loop will run at most 1000 times and L(M3) = L3.
- The language L4 is equal to the language ATM and hence we know that it is undecidable.
- The language L5 is undecidable. A proof of it is given i Exercise 4.