Two-way finite automaton: Difference between revisions

Revision as of 14:58, 20 February 2019

Revision as of 08:41, 7 March 2019

Line 19:

| doi = 10.1147/rd.32.0114

| access-date =

}}</ref> who proved them to have equivalent power to one-way [[Deterministic finite automaton|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 kinds of machines recognize precisely the class of [[regular language]]s. However, the equivalent DFA for a 2DFA may requiresrequire exponentially many states, making 2DFAs a much more practical representation for algorithms for some common problems.

2DFAs 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).