Two-way finite automaton: Difference between revisions

Revision as of 15:39, 30 October 2021

Latest revision as of 06:31, 14 April 2025

(4 intermediate revisions by 3 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 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]]