Content deleted Content added
No edit summary |
|||
Line 7:
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 ==
Formally, a two-way deterministic finite automaton can be described by the following 8-[[tuple]]: <math>M=(Q,\Sigma,L,R,\delta,s,t,r)</math> where
Line 29:
: <math>\delta(t,R)=(t,L)</math>
: <math>\delta(r,R)=(r,L)</math>
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.<ref>This definition has been taken from lecture notes of CS682 (Theory of Comoputation) by Dexter Kozen of Stanford University</ref>
==Two-way quantum finite automaton==
| |||