Two-way DFA

from Wikipedia, the free encyclopedia

In computer science , a two-way deterministic finite automaton ( two-way DFA , 2DFA ) is an automaton , more precisely a deterministic finite automaton (DFA) that can revisit characters that have already been read. As in the DFA, there is also a finite number of states in the 2DFA, which are connected to one another by transitions taking into account the character to be read. In addition, each transition is also marked with the information whether the machine changes its reading position to the left or to the right. 2DFAs can therefore also be viewed as read-only Turing machines with a read- only input tape.

2DFAs can be shown to have the same thickness as DFAs; that is, every formal language that is recognized by a 2DFA can also be recognized by a DFA, which only processes all characters in the sequence. Since DFAs are obviously a special case of 2DFAs, both automata recognize exactly the set of regular languages . However, the DFA equivalent to 2DFA can have exponentially more states, which makes 2DFA a lot more practical for algorithms for some basic problems. They are also equivalent to read-only Turing machines that only have a constant amount of space on the working tape, since any constant amount of information can be brought into the finite control state via product formation (one state for every combination of working tape and control state).

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

credentials