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 nur zwei Aktionen durchführen. 
POP : Löschen des aktuellen Zeichens und einen Schritt in Richtung des Keller-Endes.
PUSH c : einen Schritt weg vom Keller-Ende machen und  dort das Zeichen c schreiben.

Kellerautomat

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