Question

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$\left\{a^n{b}^n{c}^n|n\ge 0\right\}$ .

• a. Let ${\mathbf{A}}_{\mathbf{2}\mathbf{DFA}}=\{<\mathbf{M},\mathbf{x}\mathbf{>}|\mathbf{M}$is a 2DFA and M accepts$x\overline{)\}}$ . Show that A_2DFA is decidable.
• b. Let ${\mathbf{E}}_{\mathbf{2}\mathbf{DFA}}=\{<\mathbf{M}\mathbf{>}|\mathbf{M}$is a 2DFA and $\mathbf{L}\left(\mathbf{M}\right)=\varnothing \}$. Show that E_2DFA is not decidable.

Short answer

• (a) A_2DFA is decidable.
• (b) E_2DFA is undecidable

Step-by-step solution

Decidable

A problem is decidable if there exist Turing Machine exist which will halt in finite amount of time.

Solution (a).

(a)

Let a be the number of stages in M which is a 2DFA.

Now, on input string ‘x’, there is at most $s{\left(\left|x\right|+2\right)}^2$unique configurations for M.

Thus, to know if ‘x’ accept byM , run M for at most s(|x|+2)² steps. Since it is done in finite state, so it shows that M decide A_2DFA.

Since M is decidable so A_2DFA is decidable.

Solution (b).

In this, assume, that E_2DFA is decidable. Let D be Turning Machine which can decide E_2DFA. Now design a Turing Machine E which is similar to D for deciding E_TM as:

$M=oninput\left(M\right)$

• ·Construct M' which is 2DFA that recognize M
• ·Run D on M'
• ·If D accepts, M' accept

Else

If D rejects, then M' rejects.

Since, E_TM is undecidable, so D not decide E_TM. Hence E_2DFA is not decidable by M' as M' is modelled on base of D .

Hence, E_2DFA is undecidable.