Two-way 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 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 requires 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,\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.

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

State complexity tradeoffs

Two-way and one-way finite automata, deterministic and nondeterministic, 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. Kapoutsis determined that transforming an $n$-state 2DFA to an equivalent DFA requires $n(n^{n}-(n-1)^{n})$ states in the worst case. If an $n$-state 2DFA or a 2NFA is transformed to an NFA, the worst-case number of states required is ${\binom {2n}{n+1}}=O({\frac {4^{n}}{\sqrt {n}}})$.

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

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