Zweiwege-DFA

In der Informatik ist ein Zweiwege deterministischer endlicher Automat (Zweiwege-DFA, 2DFA) ein Automat, genauer gesagt ein deterministischer endlicher Automat (DFA), der bereits gelesene Zeichen noch einmal besuchen kann. Wie im DFA gibt es auch im 2DFA eine endliche Anzahl an Zuständen, die durch Transitionen unter Beachtung des zu lesenden Zeichens miteinander verbunden sind. Darüber hinaus ist jede Transition auch mit der Information gekennzeichnet, ob der Automat seine Leseposition nach links oder nach rechts ändert. 2DFAs können demnach auch als schreibgeschützte Turingmaschine mit nur lesbarem Eingabeband betrachtet werden.

Für 2DFAs kann man zeigen, dass sie dieselbe Mächtigkeit haben wie DFAs; das heißt, jede formale Sprache, die von einem 2DFA erkannt wird, kann auch von einem DFA, der lediglich alle Zeichen in der Reihenfolge abarbeitet, erkannt werden. Da DFAs offensichtlich ein Spezialfall der 2DFAs sind, erkennen beide Automaten genau die Menge der regulären Sprachen. Jedoch kann der zum 2DFA äquivalente DFA exponentiell mehr Zustände haben, was den 2DFA für Algorithmen einiger Grundprobleme um einiges praktischer macht. Sie sind auch äquivalent zu schreibgeschützten Turingmaschinen, die nur eine gleichbleibende Menge an Platz auf dem Arbeitsband haben, da jede konstante Menge an Information in den endlichen Kontrollzustand über eine Produktbildung eingebracht werden kann (ein Zustand für jede Kombination von Arbeitsband und Kontrollzustand).

Das Konzept der 2DFAs geht auf Michael O. Rabins und Dana Scotts Arbeit Finite automata and their decision problems zurück und wurde 1997 von John Watrous' On the Power of 2-Way Quantum Finite State Automata zu Quantenautomaten verallgemeinert, in der er zeigt, dass diese Automaten auch nichtreguläre Sprachen erkennen können und somit noch mächtiger sind als 2DFAs.

Referenzen

• Guram Bezhanishvili, Hing Leung, Jerry Lodder, David Pengelley, Desh Ranjan: Two-Way Deterministic Finite Automata (PDF; 115 kB).
• Michael O. Rabin, Dana Scott: Finite automata and their decision problems. In: IBM Journal of Research and Development, 3, 114–125. 1959.
• John Watrous: On the Power of 2-Way Quantum Finite State Automata. CS-TR-1997-1350. 1997.