Two-way finite automaton: Difference between revisions

Revision as of 05:32, 1 September 2016

Revision as of 21:24, 11 March 2017

Line 1:

In [[computer science]], in particular in [[automata theory]], an automaton is called '''two-way''' if it is allowed to re-read its input.

== Two-way deterministic finite automaton ==

Line 5:

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.

2DFAs were introduced in a seminal 1959 paper by [[Michael O. Rabin|Rabin]] and [[Dana Scott|Scott]]<ref>{{cite journal

2DFAs can be shown to have equivalent power to 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 machines recognize precisely the set of [[regular language]]s. However, the equivalent DFA for a 2DFA may have exponentially more states, making 2DFAs a much more practical representation for algorithms for some common problems. They 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).

| last = Rabin

| first = Michael O.

| last2 = Scott

| first2 = Dana

| date = 1959

| title = Finite automata and their decision problems

| url =

| journal = IBM Journal of Research and Development

| volume = 3

| issue = 2

| pages = 114-125

| doi = 10.1147/rd.32.0114

| access-date =

2DFAs}}</ref>, canwho beproved shownthem to have equivalent power to one-way [[Deterministic finite automaton|DFAs;]]. thatThat 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 setclass of [[regular language]]s. However, the equivalent DFA for a 2DFA may haverequires exponentially moremany states, making 2DFAs a much more practical representation for algorithms for some common problems. They 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).

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

== Formal description ==

Line 30 ⟶ 46:

: <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 Comoputation) 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 \{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.

==State complexity tradeoffs==

Two-way and one-way finite automata, deterministic and nondeterministic, 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

| last = Kapoutsis

| year = 2005

| conference = MFCS 2005

| editor = Joanna Jedrzejowicz, Andrzej Szepietowski:

| volume = 3618

| book-title = Mathematical Foundations of Computer Science

| publisher = Springer

| ___location =

| pages = 544-555

| isbn = 978-3-540-28702-5

| 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}</math>.

==Two-way quantum finite automaton==

The concept of 2DFAs, originated by [[Michael O. Rabin|Rabin]] and [[Dana Scott|Scott]] in their 1959 seminal work "Finite automata and their decision problems", 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. [ftp://ftp.cs.wisc.edu/pub/techreports/1997/TR1350.pdf pdf]</ref>