Two-way finite automaton: Difference between revisions

Revision as of 11:12, 30 October 2021

Latest revision as of 06:31, 14 April 2025

(8 intermediate revisions by 5 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.

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 alphabetsymbols

* <math>L</math> is the left endmarker

* <math>R</math> is the right endmarker

Line 40 ⟶ 41:

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

Line 92 ⟶ 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

Line 126 ⟶ 128:

| pages = 195–202

| doi = 10.1016/0022-0000(80)90034-3

| doi-access= free

}}</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 132 ⟶ 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. [https://ftp.cs.wisc.edu/pub/techreports/1997/TR1350.pdf pdf]</ref>

==Two-way pushdown automaton==

Line 140 ⟶ 142:

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=free}}</ref>

== References ==

{{reflist}}

[[Category:Finite-state automatamachines]]