# Define a two-headed finite automaton (2DFA) to be a deterministic finite automaton that has two read-only, bidirectional

## 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 {a^{n}b^{n}c^{n}| n ≥ 0}.

a. Let A_{2DFA} = {〈M, x〉| M is a 2DFA and M accepts x}. Show that A_{2DFA} is decidable.

b. Let E_{2DFA} = {〈M〉| M is a 2DFA and L(M) = ⌀}. Show that E2DFA is not decidable.

## Step by Step Answer:

**Related Book For**