SGT Sheet

Question 1

To show that a DFA has an empty language, we must show that it never reaches an accepting state.

Algorithm:

• Run BFS or DFS from the starting position.
• If we find an accepting state, terminate and return false.
• If we do not end up finding any accepting state, return true.

We know that the DFA is finite of some $n$ states. We can simply implement the search using a Turing Machine. As we can create a Turing Machine for our algorithm prior, this means the problem is decidable and hence the Emptiness problem for DFAs is decidable.

Question 2

$$\begin{array}{rl}L(A)\cup L(B)& \text{ is regular (can construct NFA; jump to each DFA)}\\ L(A)\cap L(B)& \text{ is regular (can run each DFA after each other)}\\ \overline{L(A)}& \text{ is regular (can construct DFA; flip accept / reject)}\\ L(B)-L(A)& \equiv L(A)\cap \overline{L(B)}\\ & \\ (L(A)\cap \overline{L(B)})\cup (L(B)\cap \overline{L(A)})& \text{ is everything but the intersection}\\ E_{DFA}(L(A)\cap \overline{L(B)})\cup (L(B)\cap \overline{L(A)})& \text{ as required}\end{array}$$

Hence we can decide if the two languages are equivalent if the last line is false. This proves the Equivalence problem is decidable as we already proved that the Emptiness problem is decidable.

rewrite to make it look nicer

Question 3

Assume there is an algorithm accept(code(M), w) that is decidable, which means it is:

• Sound
• Complete
• Terminating

And it is defined as such:

$$accept(code(M),w)=\{\begin{array}{ll}1& \text{if }M(w)=1\\ 0& \text{if }M(w)=0\text{ or }M(w)=\uparrow \end{array}$$

Create a new machine $M^{\ast }$:

For the rejecting problem, we would want to output $1$ for $1$ and $0$ for $0$.

Similarly for the finite space problem.

We want to run $M^{\ast }(code(M^{\ast }))$:

• If $M^{\ast }(code(M^{\ast }))=1$ then $M^{\ast }(code(M^{\ast }))=0$.
• If $M^{\ast }(code(M^{\ast }))=0$ then $M^{\ast }(code(M^{\ast }))=1$. This is a contradiction, which means the accepting problem for Turing machines is undecidable.