Define a two-headed finite automaton $(2DFA)$ to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the input tape and can be independently controlled to move in either direction. The tape of a $2DFA$ is finite and is just large enough to contain the input plus two additional blank tape cells, one on the left-hand end and one on the right-hand end, that serve as delimiters. A $2DFA$ accepts its input by entering a special accept state. For example, a $2DFA$ can recognize the language $\{a^{n}b^{n}c^{n}\mid n\geq 0\}$.
- Let $A_{2DFA} = \{ \langle M, x \rangle \mid \text {M is a 2DFA and M accepts}\: x\}$. Show that $A_{2DFA}$ is decidable.
- Let $E_{2DFA} = \{\langle M \rangle \mid \text{M is a 2DFA and} \:L(M) = \emptyset\}$. Show that $E_{2DFA}$ is not decidable.
