Two-way finite automaton

From HandWiki
Short description: Type of finite automaton in automata theory

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

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

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

  • For all [math]\displaystyle{ q \in Q }[/math]
[math]\displaystyle{ \delta(q,L)=(q^\prime,\mathrm{right}) }[/math] for some [math]\displaystyle{ q^\prime \in Q }[/math]
[math]\displaystyle{ \delta(q,R)=(q^\prime,\mathrm{left}) }[/math] for some [math]\displaystyle{ q^\prime \in Q }[/math]

It says that there must be some transition possible when the pointer reaches either end of the input word.

[math]\displaystyle{ \delta(t,\sigma)=(t,R) }[/math]
[math]\displaystyle{ \delta(r,\sigma)=(r,R) }[/math]
[math]\displaystyle{ \delta(t,R)=(t,L) }[/math]
[math]\displaystyle{ \delta(r,R)=(r,L) }[/math]

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

  • [math]\displaystyle{ \delta: Q \times (\Sigma \cup \{L,R\}) \rightarrow 2^{Q \times \{\mathrm{left,right}\}} }[/math].

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

  • [math]\displaystyle{ Q=Q_\exists \cup Q_\forall }[/math] where [math]\displaystyle{ Q_\exists \cap Q_\forall=\emptyset }[/math].

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

Question, Web Fundamentals.svg Unsolved problem in computer science:
Does every [math]\displaystyle{ n }[/math]-state 2NFA have an equivalent [math]\displaystyle{ \operatorname{poly}(n) }[/math]-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 [math]\displaystyle{ 2^n }[/math] 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. MFCS 2005. 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. 8634. pp. 291–302. doi:10.1007/978-3-662-44522-8_25. ISBN 978-3-662-44521-1. 
  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". 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. https://archive.org/details/introductiontoau00hopc.  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. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Two-way_finite_automaton&oldid=3432313"