Two-way finite automaton: Difference between revisions

Revision as of 09:12, 9 May 2018

Latest revision as of 06:31, 14 April 2025

(22 intermediate revisions by 14 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.

== 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 machine]]s with no work tape, only a read-only input tape.

Line 19 ⟶ 20:

| 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 requiresrequire 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).

Line 26 ⟶ 27:

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

* {{mvar|<math>Q}}</math> is the finite, non-empty set of ''states''

* {{<math|&>\Sigma;}}</math> is the finite, non-empty set of input alphabetsymbols

* {{mvar|<math>L}}</math> is the left endmarker

* {{mvar|<math>R}}</math> is the right endmarker

* <math>\delta: Q \times (\Sigma \cup \{L,R\}) \rightarrow Q \times \{\textmathrm{left,right}\}</math>

* {{mvar|<math>s}}</math> is the start state

* {{mvar|<math>t}}</math> is the end state

* {{mvar|<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,\textmathrm{right})</math> for some <math>q^\prime \in Q</math>

:<math>\delta(q,R)=(q^\prime,\textmathrm{left})</math> for some <math>q^\prime \in Q</math>

It says that there must be some transition possible when the pointer onreaches theeither alphabetend reachesof the endinput 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 ComoputationComputation) 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 \{\textmathrm{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.

Line 57 ⟶ 58:

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.

Line 64 ⟶ 65:

{{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|Kapoutsis]]<ref>{{cite conference

| title = Removing Bidirectionality from Nondeterministic Finite Automata

| first = Christos

Line 77 ⟶ 78:

| pages = 544–555

| doi = 10.1007/11549345_47

}}</ref> determined that transforming an {{mvar|<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 {{mvar|<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>

proved that an {{mvar|n}}-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 {{mvar|<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

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.

Line 97 ⟶ 93:

| 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

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

Line 109 ⟶ 104:

| 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

and the [[L (complexity)|L]] vs. [[NL (complexity)|NL]] open problem,

see [[Kapoutsis, Christos|Kapoutsis]]<ref>{{cite journal

| last = Kapoutsis

| first = Christos A.

Line 135 ⟶ 128:

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

Line 140 ⟶ 134:

The concept of 2DFAs was in 1997 generalized to [[quantum computing]] by [[John Watrous (computer scientist)|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 (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. [ftphttps://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-X8| 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>

it has been studied by Hartmanis, Lewis, and Stearns (1965).

Aho, Hopcroft, Ullman (1968)<ref>{{cite bookjournal|author1=JAlfred V. HartmanisAho |author2=P.M. {Lewis II },John R.E. StearnsHopcroft | chapterauthor3=HierarchiesJeffrey of MemoryD. LimitedUllman Computations| title=Proc.Time 6thand Ann.Tape IEEEComplexity Symp.of onPushdown SwitchingAutomaton CircuitLanguages| Theoryjournal=Information and Logical DesignControl| year=19651968| volume=13| number=3| pages=179–190186–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;

Aho, Hopcroft, Ullman (1968)

Gray, Harrison, and Ibarra (1967) investigated the closure properties of these languages.<ref>{{cite journal|author1=AlfredJim V. AhoGray |author2=JohnMichael EA. HopcroftHarrison |author3=JeffreyOscar DH. UllmanIbarra | title=Time and Tape Complexity ofTwo-Way Pushdown Automaton LanguagesAutomata| journal=Information and Control| year=19681967| volume=1311| number=31–2| pages=186–20630–70| doi=10.1016/s0019-9958(6867)9108790369-5| doi-access=}}</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}}</ref>

== References ==

{{reflist}}

[[Category:Finite-state automatamachines]]