Home -> Themen -> Kellerautomat


Turing-Werkstatt

Theoretische Informatik am PC


O.Pletsch 1862 Kellerautomat

Ein Kellerautomat besitzt ein Band für die Eingabe. Die Eingabe wird nur gelesen. Daher sind dem zugehörigen S/L-Kopf nur die Bewegungen R, N, S erlaubt. Zusätzlich besitzt der Kellerautomat einen Kellerspeicher. Das ist ein einseitig unendliches Band. Die erste Zelle diese Bandes enthält das Zeichen für das Ende des Kellers. Der S/L-Kopf kann zwei Aktionen durchführen. 
PUSH c : einen Schritt vom Keller-Ende weg machen und dort das Zeichen c schreiben.
POP : Löschen des aktuellen Zeichens und einen Schritt in Richtung des Keller-Endes machen.

Kellerautomat

Video : Turing-Werkstatt,Teil4
Tipps zur Formulierung von deterministischen Kellerrautomaten mit Turing-Werkstatt.
Als Beispiel dient eine Turing-Maschine, die entscheidet, ob ein Wort die Buchstaben a und b gleich oft enthält..

Simulation von Kellerautomaten mit Turing-Werkstatt
Man erzeugt eine Turing-Maschine mit zwei Bändern. 
Auf Band1, dem Eingabeband, sind dem S/L-Kopf nur die Bewegungsrichtungen R, N und S erlaubt. Jedes gelesene Zeichen wird nicht verändert.
Auf Band2. dem Keller-Band, kann ein Zeichen gelöscht werden, das bedeutet Schreiben eines Leerzeichens, und Schritt zum Keller-Ende hin oder es wird ein Zeichen c auf den Kellerspeicher gebracht (PUSH c). Dazu entfernt sich der S/L-Kopf um einen Schritt vom Keller-Ende und schreibt dann das Zeichen c. 
Bei einem PUSH-Befehl müssen in Turing-Werkstatt die Bewegungen P oder H verwendet werden. 
P : Keller-Ende ist rechts vom aktuellen Feld des Keller-Bandes, 
H : Keller-Ende ist links vom aktuellen Feld des Keller-Bandes.

Ein Beispiel :
KA-a=b.tm ist ein Kellerautomat, der alle Worte über {a,b} erkennt, in denen die Buchstaben a und b gleich oft vorkommen.
Die Maschine durchläuft das Eingabewort w von links nach rechts und speichert auf dem Kellerband den Überschuss an den Zeichen a oder b. Ist nach dem Durchlauf nur noch das Symbol des Keller-Endes übrig, so ist w akzeptiert. Akzeptanz durch Leeren des Kellers.

Download aller Beispiele


Letzte Änderung : 15.3.2018