Two-way deterministic finite automaton

In computer science, a two-way deterministic finite automaton ( DFA Two-way, 2DFA ) is a machine, more precisely, a deterministic finite automaton ( DFA ), the characters already read can visit again. As there are in the DFA 2DFA a finite number of states that are connected by transitions in accordance with the character to be read. Furthermore, each transition is identified with information as to whether the machine changes its reading position to the left or to the right. 2DFAs can therefore also be considered as read-only Turing machine with only legible input tape.

For 2DFAs one can show that they have the same cardinality as DFA; That is, each formal language, which is recognized by a 2DFA can be recognized by a DFA merely executes all the characters in the sequence. Since DFAs are obviously a special case of 2DFAs, both machines recognize exactly the set of regular languages. However, the DFA equivalent to 2DFA can have exponentially more states, which makes the 2DFA algorithms for some fundamental problems of a practical lot. They are also equivalent to read-only Turing machines which have only a constant amount of space on the work tape, since any constant amount of information in the finite control state can be introduced via a product formation (one state for each combination of work tape and control condition).

The concept of 2DFAs goes back to Michael O. Rabin and Dana Scott's work finite automata and Their decision problems and was founded in 1997 by John Watrous ' On the Power of 2- Way Quantum Finite State Automata generalized to quantum automata, in which he shows that these machines also can recognize non-regular languages ​​, and thus are more powerful than 2DFAs.

Credentials

  • Michael O. Rabin, Dana Scott: Finite automata and Their decision problems. In: IBM Journal of Research and Development, 3, 114-125. In 1959.
  • John Watrous: On the Power of 2- Way Quantum Finite State Automata. CS -TR -1997- 1350. In 1997.
  • Automata Theory
838113
de