Content deleted Content added
m Moving Category:Finite automata to Category:Finite-state machines per Wikipedia:Categories for discussion/Speedy |
|||
| (44 intermediate revisions by 24 users not shown) | |||
Line 1:
{{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.
==
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 machine]]s with no work tape, only a read-only input tape.
2DFAs were introduced in a seminal 1959 paper by [[Michael O. Rabin|Rabin]] and [[Dana Scott|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 [[Deterministic finite automaton|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 language]]s. 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 machine]]s 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
* <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
Line 21 ⟶ 38:
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
* 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 [[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 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>. [[Richard E. 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 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 [[Michael Sipser|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 (complexity)|L]] vs. [[NL (complexity)|NL]] open problem, see [[Christos Kapoutsis|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. [[Michael Sipser|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
<ref>[[John Watrous (computer scientist)|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. [
==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
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
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=
== References ==
{{reflist}}
[[Category:Finite-state machines]]
| |||