Content deleted Content added
→State complexity tradeoffs: html math formatting doesn't work inside the unsolved template |
m Moving Category:Finite automata to Category:Finite-state machines per Wikipedia:Categories for discussion/Speedy |
||
| (26 intermediate revisions by 15 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 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
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 27 ⟶ 28:
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 37 ⟶ 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
== 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.
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
| 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 <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.
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
| 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
| 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. [
==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=
▲<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>
== References ==
{{reflist}}
[[Category:Finite-state
| |||