{{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,<ref>{{cite journal | last = Rabin | first = Michael O. | last2 = Scott | first2 = Dana | date = 1959 | title = Finite automata and their decision problems | url = | journal = IBM Journal of Research and Development | volume = 3 | issue = 2 | pages = 114–125 | doi = 10.1147/rd.32.0114 | access-date = }}</ref> 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>M=(Q,\Sigma,L,R,\delta,s,t,r)</math> where * <math>Q</math> is the finite, non-empty set of ''states'' * <math>\Sigma</math> is the finite, non-empty set of input symbols * <math>L</math> is the left endmarker * <math>R</math> is the right endmarker * <math>\delta: Q \times (\Sigma \cup \{L,R\}) \rightarrow Q \times \{\mathrm{left,right}\}</math> * <math>s</math> is the start state * <math>t</math> is the end state * <math>r</math> is the reject state
In addition, the following two conditions must also be satisfied: * For all <math>q \in Q</math> :<math>\delta(q,L)=(q^\prime,\mathrm{right})</math> for some <math>q^\prime \in Q</math> :<math>\delta(q,R)=(q^\prime,\mathrm{left})</math> for some <math>q^\prime \in Q</math> It says that there must be some transition possible when the pointer reaches either end of the input word. * For all symbols <math>\sigma \in \Sigma \cup \{L\}</math>{{clarify|reason='L' and 'R' are not allowed in the 2nd component of a \delta result. Probably, in the right hand side of the following 4 equations, 'L' should be fixed to 'left' and 'R' to 'right'?|date=October 2021}} : <math>\delta(t,\sigma)=(t,R)</math> : <math>\delta(r,\sigma)=(r,R)</math> : <math>\delta(t,R)=(t,L)</math> : <math>\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.<ref>This definition has been taken from lecture notes of CS682 (Theory of Computation) by Dexter Kozen of Stanford University</ref>
== 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>\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>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 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<ref>{{cite conference | title = Removing Bidirectionality from Nondeterministic Finite Automata | first = Christos | last = Kapoutsis | year = 2005 | conference = MFCS 2005 | editor = J. Jedrzejowicz, A.Szepietowski | volume = 3618 | book-title = Mathematical Foundations of Computer Science | publisher = Springer | location = | 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\left(\frac{4^n}{\sqrt{n}}\right)</math>. Ladner, Lipton and 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 Geffert and Okhotin.<ref name="GeffertOkhotin2014">{{cite book|last1=Geffert|first1=Viliam|title=Mathematical Foundations of Computer Science 2014|last2=Okhotin|first2=Alexander|chapter=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|series=Lecture Notes in Computer Science|isbn=978-3-662-44521-1}}</ref>
{{unsolved|computer science|Does every <math>n</math>-state 2NFA have an equivalent <math>\operatorname{poly}(n)</math>-state 2DFA?}} 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,<ref>{{cite conference | title = Nondeterminism and the Size of Two Way Finite Automata | first1 = William J. | last1 = Sakoda | first2 = Michael | last2 = Sipser | year = 1978 | conference = STOC 1978 | publisher = ACM | location = | pages = 275–286 | doi = 10.1145/800133.804357 | doi-access = free }}</ref> who compared it to the P vs. NP problem in the computational complexity theory. Berman and Lingas<ref>{{cite conference | title = On the complexity of regular languages in terms of finite automata | first1 = Piotr | last1 = Berman | first2 = Andrzej | last2 = Lingas | year = 1977 | volume = Report 304 | publisher = Polish Academy of Sciences }}</ref> discovered a formal relation between this problem and the L vs. NL open problem, see Kapoutsis<ref>{{cite journal | last = Kapoutsis | first = Christos A. | date = 2014 | title = Two-Way Automata Versus Logarithmic Space | journal = Theory of Computing Systems | volume = 55 | issue = 2 | pages = 421–447 | doi = 10.1007/s00224-013-9465-0 }}</ref> 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<ref>{{cite journal | last = Sipser | first = Michael | date = 1980 | title = Lower Bounds on the Size of Sweeping Automata | journal = Journal of Computer and System Sciences | volume = 21 | issue = 2 | pages = 195–202 | doi = 10.1016/0022-0000(80)90034-3 | doi-access= }}</ref> 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>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. <ref>John Watrous. [http://citeseer.ist.psu.edu/article/watrous97power.html On the Power of 2-Way Quantum Finite State Automata]. CS-TR-1997-1350. 1997. [https://ftp.cs.wisc.edu/pub/techreports/1997/TR1350.pdf pdf]</ref>
==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''');<ref>{{cite book| author1=John E. Hopcroft| author2=Jeffrey D. Ullman| title=Introduction to Automata Theory, Languages, and Computation| year=1979| publisher=Addison-Wesley| isbn=978-0-201-02988-8| url-access=registration| url=https://archive.org/details/introductiontoau00hopc}} Here: p.124; this paragraph is omitted in the 2003 edition.</ref> it has been studied by Hartmanis, Lewis, and Stearns (1965).<ref>{{cite book|author1=J. Hartmanis |author2=P.M. Lewis II, R.E. Stearns| chapter=Hierarchies of Memory Limited Computations| title=Proc. 6th Ann. IEEE Symp. on Switching Circuit Theory and Logical Design| year=1965| pages=179–190}}</ref> Aho, Hopcroft, Ullman (1968)<ref>{{cite journal|author1=Alfred V. Aho |author2=John E. Hopcroft |author3=Jeffrey D. Ullman | title=Time and Tape Complexity of Pushdown Automaton Languages| journal=Information and Control| year=1968| volume=13| number=3| pages=186–206| doi=10.1016/s0019-9958(68)91087-5| doi-access=free}}</ref> and Cook (1971)<ref>{{cite book| author=S.A. Cook| chapter=Linear Time Simulation of Deterministic Two-Way Pushdown Automata| title=Proc. IFIP Congress| year=1971| pages=75–80| publisher=North Holland}}</ref> 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.<ref>{{cite journal|author1=Jim Gray |author2=Michael A. Harrison |author3=Oscar H. Ibarra | title=Two-Way Pushdown Automata| journal=Information and Control| year=1967| volume=11| number=1–2| pages=30–70| doi=10.1016/s0019-9958(67)90369-5| doi-access=}}</ref>
== References == {{reflist}}
Category:Finite-state machines