Two-way finite automaton: Difference between revisions

Revision as of 17:33, 6 October 2015

Revision as of 17:35, 6 October 2015

Line 4:

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.

We think of the symbols of the input string as occupying cells of a finite

tape, one symbol per cell. The input string is enclosed in left and right

endmarkers ` and a, which are not elements of the input alphabet �. The

read head may not move outside of the endmarkers.

Informally, the machine starts in its start state s with its read head pointing

to the left endmarker. At any point in time, the machine is in some state q

with its read head scanning some tape cell containing an input symbol ai or

one of the endmarkers. Based on its current state and the symbol occupying

the tape cell it is currently scanning, it moves its read head either left or

right one cell and enters a new state. It accepts by entering a special accept

state t and rejects by entering a special reject state r. The machine’s action

on a particular state and symbol is determined by a transition function �

that is part of the specification of the machine

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