Content deleted Content added
→State complexity tradeoffs: Wrote about the 2DFA vs 2NFA problem |
Added a section on sweeping automata |
||
Line 110:
| 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
}}</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==
Line 132 ⟶ 146:
{{reflist}}
* Hing Leung. [http://www.math.nmsu.edu/hist_projects/2DFA.pdf Two-Way Deterministic Finite Automata].
[[Category:Finite automata]]
| |||