Two-way finite automaton: Difference between revisions

Content deleted Content added

Inline

Revision as of 21:53, 25 March 2017

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,^[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 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.^[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

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

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

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. Kapoutsis^[3] 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}}})$ . Ladner, Lipton and Stockmeyer.^[4] proved that an $n$ -state 2AFA can be converted to a DFA with $2^{n2^{n}}$ states. The 2AFA to NFA conversion requires $2^{\Theta (n\log n)}$ states in the worst case, see Geffert and Okhotin.^[5]

Unsolved problem in computer science:

Does every n-state 2NFA have an equivalent 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 $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

^ 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.
^ This definition has been taken from lecture notes of CS682 (Theory of Comoputation) by Dexter Kozen of Stanford University
^ 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.
^ 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.
^ Geffert, Viliam; Okhotin, Alexander (2014). "Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata". 8634: 291–302. doi:10.1007/978-3-662-44522-8_25. ISSN 0302-9743. {{cite journal}}: Cite journal requires |journal= (help)
^ 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.
^ Berman, Piotr; Lingas, Andrzej (1977). On the complexity of regular languages in terms of finite automata. Vol. Report 304. Polish Academy of Sciences.
^ 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.
^ 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.
^ John Watrous. On the Power of 2-Way Quantum Finite State Automata. CS-TR-1997-1350. 1997. pdf
^ 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.
^ 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.
^ 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.
^ S.A. Cook (1971). "Linear Time Simulation of Deterministic Two-Way Pushdown Automata". Proc. IFIP Congress. North Holland. pp. 75–80.
^ 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.

[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 Comoputation) 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.

[LadnerLipton1984-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.

[GeffertOkhotin2014-5] Geffert, Viliam; Okhotin, Alexander (2014). "Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata". 8634: 291–302. doi:10.1007/978-3-662-44522-8_25. ISSN 0302-9743. {{cite journal}}: Cite journal requires |journal= (help)

[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 0-201-02988-X. 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

@@ Line 49: / Line 49: @@
 == 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
+A ''two-way nondeterministic finite automaton'' (2NFA) may have multiple transitions defined in the same configuration. Its transition function is
 * <math>\delta: Q \times (\Sigma \cup \{L,R\}) \rightarrow 2^{Q \times \{left,right\}}</math>.
 Like a standard one-way [[Nondeterministic finite automaton|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>Q=Q_\exists \cup Q_\forall</math> where <math>Q_\exists \cap Q_\forall=\emptyset</math>.
+States in <math>Q_\exists</math> and <math>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|State complexity}}
-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. [[Christos Kapoutsis|Kapoutsis]]<ref>{{cite conference
+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|Kapoutsis]]<ref>{{cite conference
 | title = Removing Bidirectionality from Nondeterministic Finite Automata
 | first = Christos
@@ Line 69: / Line 77: @@
 | pages = 544–555
 | doi = 10.1007/11549345_47
-}}</ref> determined that transforming an <math>n</math>-state 2DFA to an equivalent DFA requires <math>n(n^n-(n-1)^n)</math> states in the worst case. If an <math>n</math>-state 2DFA or a 2NFA is transformed to an NFA, the worst-case number of states required is <math>\binom{2n}{n+1} = O(\frac{4^n}{\sqrt{n}})</math>.
+}}</ref> determined that transforming an <math>n</math>-state 2DFA to an equivalent DFA requires <math>n(n^n-(n-1)^n)</math> states in the worst case. If an <math>n</math>-state 2DFA or a 2NFA is transformed to an NFA, the worst-case number of states required is <math>\binom{2n}{n+1} = O(\frac{4^n}{\sqrt{n}})</math>. [[Richard Ladner|Ladner]], [[Richard J. Lipton|Lipton]] and [[Larry Stockmeyer|Stockmeyer]].<ref name="LadnerLipton1984">{{cite journal|last1=Ladner|first1=Richard E.|last2=Lipton|first2=Richard J.|last3=Stockmeyer|first3=Larry J.|title=Alternating Pushdown and Stack Automata|journal=SIAM Journal on Computing|volume=13|issue=1|year=1984|pages=135–155|issn=0097-5397|doi=10.1137/0213010}}</ref>
+proved that an <math>n</math>-state 2AFA can be converted to a DFA with <math>2^{n2^n}</math> states.
+The 2AFA to NFA conversion requires <math>2^{\Theta(n \log n)}</math> states in the worst case,
+see [[Viliam Geffert|Geffert]] and [[Alexander Okhotin|Okhotin]].<ref name="GeffertOkhotin2014">{{cite journal|last1=Geffert|first1=Viliam|last2=Okhotin|first2=Alexander|title=Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata|volume=8634|year=2014|pages=291–302|issn=0302-9743|doi=10.1007/978-3-662-44522-8_25}}</ref>
 {{unsolved|computer science|Does every n-state 2NFA have an equivalent poly(n)-state 2DFA?}}