In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input.
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 value indicating whether the machine will move its position in the input to the left, right, or stay at the same position.
2DFAs were introduced in a seminal 1959 paper by Rabin and Scott,[1] who proved them to have equivalent power to one-way DFAs.
Since DFAs are obviously a special case of 2DFAs, this implies that both kinds of machines recognize precisely the class of regular languages.
However, the equivalent DFA for a 2DFA may require exponentially many states, making 2DFAs a much more practical representation for algorithms for some common problems.
Formally, a two-way deterministic finite automaton can be described by the following 8-tuple:
where In addition, the following two conditions must also be satisfied: It says that there must be some transition possible when the pointer reaches either end of the input word.
It says that once the automaton reaches the accept or reject state, it stays in there forever and the pointer goes to the right most symbol and cycles there infinitely.
[2] A two-way nondeterministic finite automaton (2NFA) may have multiple transitions defined in the same configuration.
Two-way and one-way finite automata, deterministic and nondeterministic and alternating, accept the same class of regular languages.
-state 2DFA or a 2NFA is transformed to an NFA, the worst-case number of states required is
[5] It is an open problem whether every 2NFA can be converted to a 2DFA with only a polynomial increase in the number of states.
Berman and Lingas[7] discovered a formal relation between this problem and the L vs. NL open problem, see Kapoutsis[8] for a precise relation.
Sweeping automata are 2DFAs of a special kind that process the input string by making alternating left-to-right and right-to-left sweeps, turning only at the endmarkers.
The concept of 2DFAs 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 DFAs.
[10] A pushdown automaton that is allowed to move either way on its input tape is called two-way pushdown automaton (2PDA);[11] it has been studied by Hartmanis, Lewis, and Stearns (1965).
[12] Aho, Hopcroft, Ullman (1968)[13] and Cook (1971)[14] characterized the class of languages recognizable by deterministic (2DPDA) and non-deterministic (2NPDA) two-way pushdown automata; Gray, Harrison, and Ibarra (1967) investigated the closure properties of these languages.