Two-way finite automaton: Difference between revisions

Revision as of 12:27, 12 March 2017

Revision as of 18:17, 15 March 2017

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

| last = Rabin

| first = Michael O.

Line 16:

| volume = 3

| issue = 2

| pages = 114-125114–125

| 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 requires exponentially many states, making 2DFAs a much more practical representation for algorithms for some common problems.

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

| publisher = Springer

| ___location =

| pages = 544-555544–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(\frac{4^n}{\sqrt{n}})</math>.

Line 74:

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

| publisher = ACM

| ___location =

| pages = 275-286275–286

| doi = 10.1145/800133.804357

}}</ref>,

who compared it to the [[P vs. NP]] problem

in the [[computational complexity theory]].

Line 108:

| volume = 55

| issue = 2

| pages = 421-447421–447

| doi = 10.1007/s00224-013-9465-0

}}</ref> for a precise relation.

Line 122:

| volume = 21

| issue = 2

| pages = 195-202195–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.