Two-way deterministic finite automaton
From Wikipedia, the free encyclopedia
In computer science, a two-way deterministic finite automaton (2DFA) is an abstract machine, a generalized version of the deterministic finite automaton (DFA) which can revisit characters already processed. As in a DFA, there are a finite number of states with transitions between them based on the current character, but each transition is also labelled with a bit indicating whether the machine will move its position in the input to the left, right, or stay at the same position. Equivalently, 2DFAs can be seen as read-only Turing machines with no work tape, only a read-only input tape.
2DFAs can be shown to have equivalent power to DFAs; that is, any formal language which can be recognized by a 2DFA can be recognized by a DFA which only examines and consumes each character in order. Since DFAs are obviously a special case of 2DFAs, this implies that both machines recognize precisely the set of regular languages. However, the equivalent DFA for a 2DFA may have exponentially more states, making 2DFAs a much more practical representation for algorithms for some common problems. They are also equivalent to read-only Turing machines that use only a constant amount of space on their work tape, since any constant amount of information can be incorporated into the finite control state via a product construction (a state for each combination of work tape state and control state).
The concept of 2DFAs, originated by Rabin and Scott in their seminal work "Finite automata and their decision problems", was in 1997 generalized to quantum computing by John Watrous's "On the Power of 2-Way Quantum Finite State Automata", in which he demonstrates that these machines can recognize nonregular languages and so are more powerful than 2DFAs.
[edit] References
- Guram Bezhanishvili, Hing Leung, Jerry Lodder, David Pengelley, and Desh Ranjan. Two-Way Deterministic Finite Automata. http://www.math.nmsu.edu/hist_projects/2DFA.pdf.
- M. O. Rabin and D. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3, 114–125. 1959.
- John Watrous. On the Power of 2-Way Quantum Finite State Automata. CS-TR-1997-1350. 1997.
