Two-way finite automaton

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,{{cite journal | access-date =

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,\Sigma,L,R,\delta,s,t,r) where

• Q is the finite, non-empty set of states
• \Sigma is the finite, non-empty set of input symbols
• L is the left endmarker
• R is the right endmarker
• \delta: Q \times (\Sigma \cup {L,R}) \rightarrow Q \times {\mathrm{left,right}}
• s is the start state
• t is the end state
• r is the reject state

In addition, the following two conditions must also be satisfied:

• For all q \in Q :\delta(q,L)=(q^\prime,\mathrm{right}) for some q^\prime \in Q :\delta(q,R)=(q^\prime,\mathrm{left}) for some 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 \sigma \in \Sigma \cup {L} : \delta(t,\sigma)=(t,R) : \delta(r,\sigma)=(r,R) : \delta(t,R)=(t,L) : \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

• \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.

Two-way alternating finite automaton

A two-way alternating finite automaton (2AFA) is a two-way extension of an alternating finite automaton (AFA). Its state set is

• Q=Q_\exists \cup Q_\forall where Q_\exists \cap Q_\forall=\emptyset.

States in Q_\exists and Q_\forall are called existential resp. universal. In an existential state a 2AFA nondeterministically chooses the next state like an NFA, and accepts if at least one of the resulting computations accepts. In a universal state 2AFA moves to all next states, and accepts if all the resulting computations accept.

State complexity tradeoffs

Main article: State complexity

Two-way and one-way finite automata, deterministic and nondeterministic and alternating, accept the same class of regular languages. However, transforming an automaton of one type to an equivalent automaton of another type incurs a blow-up in the number of states. Christos Kapoutsis{{cite conference | book-title = Mathematical Foundations of Computer Science

It is an open problem whether every 2NFA can be converted to a 2DFA with only a polynomial increase in the number of states. The problem was raised by Sakoda and Sipser,{{cite conference | doi-access = free who compared it to the P vs. NP problem in the computational complexity theory. Berman and Lingas{{cite conference

Sweeping automata

Sweeping automata are 2DFAs of a special kind that process the input string by making alternating left-to-right and right-to-left sweeps, turning only at the endmarkers. Sipser{{cite journal | doi-access=

Two-way quantum finite automaton

The concept of 2DFAs 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 DFAs.

Two-way pushdown automaton

A pushdown automaton that is allowed to move either way on its input tape is called two-way pushdown automaton (2PDA); it has been studied by Hartmanis, Lewis, and Stearns (1965). Aho, Hopcroft, Ullman (1968) and Cook (1971) characterized the class of languages recognizable by deterministic (2DPDA) and non-deterministic (2NPDA) two-way pushdown automata; Gray, Harrison, and Ibarra (1967) investigated the closure properties of these languages.

References

References

1. This definition has been taken from lecture notes of CS682 (Theory of Computation) by Dexter Kozen of Stanford University
2. (1984). "Alternating Pushdown and Stack Automata". [[SIAM Journal on Computing]].
3. (2014). "Mathematical Foundations of Computer Science 2014".
4. [[John Watrous (computer scientist). 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. [https://ftp.cs.wisc.edu/pub/techreports/1997/TR1350.pdf pdf]
5. (1979). "Introduction to Automata Theory, Languages, and Computation". Addison-Wesley.
6. (1965). "Proc. 6th Ann. IEEE Symp. on Switching Circuit Theory and Logical Design".
7. (1968). "Time and Tape Complexity of Pushdown Automaton Languages". [[Information and Control]].
8. [[Stephen A. Cook. (1971). "Proc. IFIP Congress". North Holland.
9. (1967). "Two-Way Pushdown Automata". Information and Control.