Content deleted Content added
No edit summary |
|||
Line 3:
== Two-way deterministic finite automaton ==
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. Equivalently, 2DFAs can be seen as [[read-only Turing machine]]s 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 language]]s. 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 machine]]s 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).
== Formal Description<ref>This definition has been taken from lecture notes of CS682 (Theory of Comoputation) by Dexter Kozen of Stanford University</ref> ==
| |||