The Gateway to Computer Science Excellence

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

- 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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,617 answers

195,897 comments

102,348 users