Michael Sipser Edition 3 Exercise 5 Question 26 (Page No. 240)
in Theory of Computation
245 views
0 votes
0 votes

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\}$.

  1. Let $A_{2DFA} = \{ \langle M, x \rangle  \mid \text {M is a 2DFA and M accepts}\: x\}$. Show that $A_{2DFA}$ is decidable.
  2. Let $E_{2DFA} = \{\langle M \rangle \mid \text{M is a 2DFA and} \:L(M) = \emptyset\}$. Show that $E_{2DFA}$ is not decidable.
in Theory of Computation
245 views

Subscribe to GO Classes for GATE CSE 2022

Please log in or register to answer this question.

Related questions