In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input.
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 machines with no work tape, only a read-only input tape. 2DFAs were introduced in a seminal 1959 paper by Rabin and Scott, who proved them to have equivalent power to one-way 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 languages. However, the equivalent DFA for a 2DFA may require exponentially many states, making 2DFAs a much more practical representation for algorithms for some common problems. 2DFAs 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).
Formal description Formally, a two-way deterministic finite automaton can be described by the following 8-tuple: M = ( Q , Σ , L , R , δ , s , t , r ) {\displaystyle M=(Q,\Sigma ,L,R,\delta ,s,t,r)} where
Q {\displaystyle Q} is the finite, non-empty set of states
Σ {\displaystyle \Sigma } is the finite, non-empty set of input symbols
L {\displaystyle L} is the left endmarker
R {\displaystyle R} is the right endmarker
δ : Q × ( Σ ∪ { L , R } ) → Q × { l e f t , r i g h t } {\displaystyle \delta :Q\times (\Sigma \cup \{L,R\})\rightarrow Q\times \{\mathrm {left,right} \}}
s {\displaystyle s} is the start state
t {\displaystyle t} is the end state
r {\displaystyle r} is the reject state In addition, the following two conditions must also be satisfied:
For all q ∈ Q {\displaystyle q\in Q}
δ ( q , L ) = ( q ′ , r i g h t ) {\displaystyle \delta (q,L)=(q^{\prime },\mathrm {right} )} for some q ′ ∈ Q {\displaystyle q^{\prime }\in Q}
δ ( q , R ) = ( q ′ , l e f t ) {\displaystyle \delta (q,R)=(q^{\prime },\mathrm {left} )} for some q ′ ∈ Q {\displaystyle q^{\prime }\in Q}
It says that there must be some transition possible when the pointer reaches either end of the input word.
For all symbols σ ∈ Σ ∪ { L } {\displaystyle \sigma \in \Sigma \cup \{L\}}
δ ( t , σ ) = ( t , R ) {\displaystyle \delta (t,\sigma )=(t,R)}
δ ( r , σ ) = ( r , R ) {\displaystyle \delta (r,\sigma )=(r,R)}
δ ( t , R ) = ( t , L ) {\displaystyle \delta (t,R)=(t,L)}
δ ( r , R ) = ( r , L ) {\displaystyle \delta (r,R)=(r,L)}
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.
Two-way nondeterministic finite automaton A two-way nondeterministic finite automaton (2NFA) may have multiple transitions defined in the same configuration. Its transition function is
δ : Q × ( Σ ∪ { L , R } ) → 2 Q × { l e f t , r i g h t } {\displaystyle \delta :Q\times (\Sigma \cup \{L,R\})\rightarrow 2^{Q\times \{\mathrm {left,right} \}}} . Like a standard one-way NFA, a 2NFA accepts a string if at least one of the possible computations is accepting. Like the 2DFAs, the 2NFAs also accept only regular languages.
… excerpt ends here. Continue reading the full article.
