Two-way deterministic finite automaton

In computer science, in particular in automata theory, an automaton is called two-way if it 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 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).

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 alphabet
• $L$ is the left endmarker
• $R$ is the right endmarker
• $\delta :Q\times (\Sigma \cup \{L,R\})\rightarrow Q\times \{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 },right)$ for some $q^{\prime }\in Q$

$\delta (q,R)=(q^{\prime },left)$ for some $q^{\prime }\in Q$

It says that there must be some transition possible when pointer on the alphabet reaches the end.

• 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.^[1]

Two-way quantum finite automaton

The concept of 2DFAs, originated by Rabin and Scott in their 1959 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 DFAs. ^[2]

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);^[3] it has been studied by Hartmanis, Lewis, and Stearns (1965). ^[4] Aho, Hopcroft, Ullman (1968) ^[5] and Cook (1971) ^[6] 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. ^[7]

References

1. This definition has been taken from lecture notes of CS682 (Theory of Comoputation) by Dexter Kozen of Stanford University
2. John Watrous. On the Power of 2-Way Quantum Finite State Automata. CS-TR-1997-1350. 1997. pdf
3. John E. Hopcroft; Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. Here: p.124; this paragraph is omitted in the 2003 edition.
4. J. Hartmanis; P.M. {Lewis II }, R.E. Stearns (1965). "Hierarchies of Memory Limited Computations". Proc. 6th Ann. IEEE Symp. on Switching Circuit Theory and Logical Design. pp. 179–190.
5. Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1968). "Time and Tape Complexity of Pushdown Automaton Languages". Information and Control. 13 (3): 186–206. doi:10.1016/s0019-9958(68)91087-5.
6. S.A. Cook (1971). "Linear Time Simulation of Deterministic Two-Way Pushdown Automata". Proc. IFIP Congress. North Holland. pp. 75–80.
7. Jim Gray; Michael A. Harrison; Oscar H. Ibarra (1967). "Two-Way Pushdown Automata". Information and Control. 11 (1–2): 30–70. doi:10.1016/s0019-9958(67)90369-5.

• Hing Leung. 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.