Two-way finite automaton

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, ^[1] 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: ${\displaystyle M=(Q,\Sigma ,L,R,\delta ,s,t,r)}$ where

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

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

• For all ${\displaystyle q\in Q}$

${\displaystyle \delta (q,L)=(q^{\prime },\mathrm {right} )}$ for some ${\displaystyle q^{\prime }\in Q}$

${\displaystyle \delta (q,R)=(q^{\prime },\mathrm {left} )}$ for some ${\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 ${\displaystyle \sigma \in \Sigma \cup \{L\}}$^{[ clarification needed ]}

${\displaystyle \delta (t,\sigma )=(t,R)}$

${\displaystyle \delta (r,\sigma )=(r,R)}$

${\displaystyle \delta (t,R)=(t,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. ^[2]

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

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

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

• ${\displaystyle Q=Q_{\exists }\cup Q_{\forall }}$ where ${\displaystyle Q_{\exists }\cap Q_{\forall }=\emptyset }$.

States in ${\displaystyle Q_{\exists }}$ and ${\displaystyle 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 ^[3] determined that transforming an ${\displaystyle n}$-state 2DFA to an equivalent DFA requires ${\displaystyle n(n^{n}-(n-1)^{n})}$ states in the worst case. If an ${\displaystyle n}$-state 2DFA or a 2NFA is transformed to an NFA, the worst-case number of states required is ${\displaystyle {\binom {2n}{n+1}}=O\left({\frac {4^{n}}{\sqrt {n}}}\right)}$. Ladner, Lipton and Stockmeyer. ^[4] proved that an ${\displaystyle n}$-state 2AFA can be converted to a DFA with ${\displaystyle 2^{n2^{n}}}$ states. The 2AFA to NFA conversion requires ${\displaystyle 2^{\Theta (n\log n)}}$ states in the worst case, see Geffert and Okhotin. ^[5]

Unsolved problem in computer science:

Does every ${\displaystyle n}$-state 2NFA have an equivalent ${\displaystyle \operatorname {poly} (n)}$-state 2DFA?

(more unsolved problems in 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, ^[6] who compared it to the P vs. NP problem in the computational complexity theory. Berman and Lingas ^[7] discovered a formal relation between this problem and the L vs. NL open problem, see Kapoutsis ^[8] for a precise relation.

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 ^[9] constructed a sequence of languages, each accepted by an n-state NFA, yet which is not accepted by any sweeping automata with fewer than ${\displaystyle 2^{n}}$ states.

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

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); ^[11] it has been studied by Hartmanis, Lewis, and Stearns (1965). ^[12] Aho, Hopcroft, Ullman (1968) ^[13] and Cook (1971) ^[14] 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. ^[15]

References

1. Rabin, Michael O.; Scott, Dana (1959). "Finite automata and their decision problems". IBM Journal of Research and Development. 3 (2): 114–125. doi:10.1147/rd.32.0114.
2. This definition has been taken from lecture notes of CS682 (Theory of Computation) by Dexter Kozen of Stanford University
3. Kapoutsis, Christos (2005). "Removing Bidirectionality from Nondeterministic Finite Automata". In J. Jedrzejowicz, A.Szepietowski (ed.). Mathematical Foundations of Computer Science. MFCS 2005. Vol. 3618. Springer. pp. 544–555. doi:10.1007/11549345_47.
4. Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J. (1984). "Alternating Pushdown and Stack Automata". SIAM Journal on Computing. 13 (1): 135–155. doi:10.1137/0213010. ISSN   0097-5397.
5. Geffert, Viliam; Okhotin, Alexander (2014). "Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata". Mathematical Foundations of Computer Science 2014. Lecture Notes in Computer Science. Vol. 8634. pp. 291–302. doi:10.1007/978-3-662-44522-8_25. ISBN   978-3-662-44521-1. ISSN   0302-9743.
6. Sakoda, William J.; Sipser, Michael (1978). Nondeterminism and the Size of Two Way Finite Automata. STOC 1978. ACM. pp. 275–286. doi: 10.1145/800133.804357 .
7. Berman, Piotr; Lingas, Andrzej (1977). On the complexity of regular languages in terms of finite automata. Vol. Report 304. Polish Academy of Sciences.
8. Kapoutsis, Christos A. (2014). "Two-Way Automata Versus Logarithmic Space". Theory of Computing Systems. 55 (2): 421–447. doi:10.1007/s00224-013-9465-0.
9. Sipser, Michael (1980). "Lower Bounds on the Size of Sweeping Automata". Journal of Computer and System Sciences. 21 (2): 195–202. doi:10.1016/0022-0000(80)90034-3.
10. John Watrous. On the Power of 2-Way Quantum Finite State Automata. CS-TR-1997-1350. 1997. pdf
11. John E. Hopcroft; Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation . Addison-Wesley. ISBN   978-0-201-02988-8. Here: p.124; this paragraph is omitted in the 2003 edition.
12. 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.
13. 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 .
14. S.A. Cook (1971). "Linear Time Simulation of Deterministic Two-Way Pushdown Automata". Proc. IFIP Congress. North Holland. pp. 75–80.
15. 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.