Two-way deterministic finite automaton
- Two-way deterministic finite automaton
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.
References
* Guram Bezhanishvili, Hing Leung, Jerry Lodder, David Pengelley, and Desh Ranjan. [http://www.math.nmsu.edu/hist_projects/2DFA.pdf Two-Way Deterministic Finite Automata] .
* M. O. Rabin and D. Scott. Finite automata and their decision problems. "IBM Journal of Research and Development", 3, 114–125. 1959.
* John Watrous. [http://citeseer.ist.psu.edu/article/watrous97power.html On the Power of 2-Way Quantum Finite State Automata] . CS-TR-1997-1350. 1997.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Deterministic finite-state machine — An example of a Deterministic Finite Automaton that accepts only binary numbers that are multiples of 3. The state S0 is both the start state and an accept state. In the theory of computation and automata theory, a deterministic finite state… … Wikipedia
Finite-state machine — State machine redirects here. For infinite state machines, see State transition system. For fault tolerance methodology, see State machine replication. SFSM redirects here. For the Italian railway company, see Circumvesuviana. A finite state… … Wikipedia
Finite state transducer — A finite state transducer (FST) is a finite state machine with two tapes: an input tape and an output tape. This contrasts with an ordinary finite state automaton (or finite state acceptor), which has a single tape. OverviewAn automaton can be… … Wikipedia
Nondeterministic finite-state machine — In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. This distinguishes … Wikipedia
Nondeterministic finite state machine — In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. This distinguishes … Wikipedia
Tree automaton — A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines. The following article deals with branching tree automata, which correspond to regular languages of… … Wikipedia
Pushdown automaton — In automata theory, a pushdown automaton (PDA) is a finite automaton that can make use of a stack containing data. Operation Pushdown automata differ from normal finite state machines in two ways: # They can use the top of the stack to decide… … Wikipedia
Quantum finite automata — In quantum computing, quantum finite automata or QFA are a quantum analog of probabilistic automata. They are related to quantum computers in a similar fashion as finite automata are related to Turing machines. Several types of automata may be… … Wikipedia
Garden of Eden (cellular automaton) — An orphan pattern in Conway s Game of Life, discovered by R. Banks in 1971.[1] … Wikipedia
Büchi automaton — A Büchi automaton is the extension of a finite state automaton to infinite inputs. It accepts an infinite input sequence iff there exists a run of the automaton (in case of a deterministic automaton, there is exactly one possible run) which… … Wikipedia
