Fachkonzept - Kellerautomat
Ein endlicher Automat mit Stapelspeicher
Ein Kellerautomat verarbeitet ein Eingabewort Zeichen für Zeichen und befindet sich dabei stets in einem Zustand. Zusätzlich besitzt er einen Keller: einen Stapelspeicher, bei dem nur das oberste Symbol zugänglich ist. Zuletzt abgelegte Symbole werden zuerst wieder entnommen. Anders als die endliche Zustandsmenge kann der Keller im Modell beliebig groß werden.
Fachkonzept: Kellerautomat
Ein Kellerautomat wird festgelegt durch:
- eine nichtleere endliche Menge von Zuständen,
- ein endliches Eingabealphabet und ein endliches Kelleralphabet,
- einen Anfangszustand und eine Menge von Endzuständen,
- ein Kellervorbelegungssymbol, hier
Z, das zu Beginn allein im Keller liegt, -
Übergänge, die in Abhängigkeit vom aktuellen Zustand, vom nächsten Eingabezeichen oder
εund vom obersten Kellersymbol einen Folgezustand und die neu abzulegenden Kellersymbole festlegen.
Bei einem Übergang wird das gelesene oberste Kellersymbol entfernt und durch die angegebenen Symbole ersetzt. Ein ε-Übergang liest kein Eingabezeichen.
Bei der hier verwendeten Akzeptanz durch Endzustand wird ein Wort akzeptiert, wenn nach vollständiger Verarbeitung der Eingabe ein Endzustand erreicht wird. Die Menge aller akzeptierten Wörter heißt Sprache des Kellerautomaten und wird mit L(K) bezeichnet.
Dieser Automat erkennt Wörter mit zuerst n öffnenden und danach n schließenden Klammern, wobei n ≥ 1 gilt: (), (()), ((())) usw. Er erkennt damit nicht alle korrekt geklammerten Ausdrücke: ()() gehört nicht zu seiner Sprache.
Das Eingabealphabet ist {(, )}, das Kelleralphabet {Z, (}. Im Zustand q0 werden öffnende Klammern abgelegt, in q1 für jede schließende Klammer wieder entfernt. q2 ist der einzige Endzustand.
Für (()) ergibt sich der folgende Lauf. In der Tabelle steht der Keller von unten nach oben: Z links, das oberste Symbol rechts.
| Schritt | Ausgeführter Übergang | Zustand | Resteingabe | Keller |
|---|---|---|---|---|
| 0 | Start | q0 | (()) |
Z |
| 1 | (|Z→Z( |
q0 | ()) |
Z( |
| 2 | (|(→(( |
q0 | )) |
Z(( |
| 3 | )|(→ |
q1 | ) |
Z( |
| 4 | )|(→ |
q1 | ε |
Z |
| 5 | ε|Z→Z |
q2 | ε |
Z |
Der letzte Übergang liest kein Zeichen und lässt Z im Keller. Erst jetzt ist ein Endzustand erreicht und die Eingabe vollständig verarbeitet: Das Wort wird akzeptiert.
Bei (() bleibt eine öffnende Klammer im Keller; der Endzustand wird nicht erreicht. Bei ()() folgt nach dem ersten Klammerpaar erneut eine öffnende Klammer, für die in q1 kein Übergang existiert. Der mögliche ε-Übergang nach q2 hilft nicht: Dort bleibt Eingabe übrig.
Die Beschriftungen an den Übergängen im Simulator haben die Form Eingabe|oberstes Kellersymbol→neu abgelegte Symbole. Die Symbole rechts vom Pfeil werden von links nach rechts abgelegt; das letzte liegt anschließend oben. Der Folgezustand ergibt sich aus dem Ziel des Übergangspfeils.
| Beschriftung | Bedeutung |
|---|---|
a|Z→Za |
a lesen; Z entfernen; zuerst Z, dann a ablegen. Das a liegt danach oben. |
b|a→ |
b lesen; das oberste a entfernen; nichts ablegen. |
ε|Z→Z |
Kein Eingabezeichen lesen; Z entfernen und wieder ablegen. Der Kellerinhalt bleibt unverändert. |
ε als Eingabesymbol bedeutet nicht „Eingabe zu Ende“: Ein ε-Übergang kann auch bei verbleibender Eingabe stattfinden, sofern Zustand und Kellersymbol passen. Ein leerer Bereich rechts vom Pfeil bedeutet, dass kein Symbol abgelegt wird.
Wann wird ein Wort akzeptiert?
Ein Wort wird akzeptiert, wenn es mindestens einen Lauf vom Anfangszustand aus gibt, der die gesamte Eingabe verarbeitet und in einem Endzustand endet. Bei einem nichtdeterministischen Kellerautomaten dürfen andere mögliche Läufe scheitern; entscheidend ist, dass mindestens ein erfolgreicher Lauf existiert.
Ein erreichter Endzustand allein genügt nicht, solange Eingabe übrig ist. Ebenso genügt ein Keller, in dem nur noch Z liegt, allein nicht zur Akzeptanz. Gibt es keinen passenden Übergang mehr, endet der betreffende Lauf. Er ist nur dann erfolgreich, wenn die Eingabe vollständig gelesen und ein Endzustand erreicht ist. Nach dem letzten Eingabezeichen können noch ε-Übergänge folgen.
Dieser DKA erkennt die Wörter mit zuerst mindestens einem a und danach genauso vielen b. Sein Anfangszustand heißt Sammeln, der einzige Endzustand Ende. In Sammeln wird pro a eine Marke abgelegt; in Abbauen entfernt jedes b eine Marke. Das Kellervorbelegungszeichen Z bleibt am Boden.
Teste die folgenden Wörter schrittweise. Beobachte besonders, ob die Eingabe bereits vollständig gelesen ist und ob der aktuelle Zustand ein Endzustand ist. In der Tabelle steht der Keller von unten nach oben, also mit Z links.
| Eingabe | Beobachtung | Ergebnis und Begründung |
|---|---|---|
ab |
Nach dem Lesen beider Zeichen: Zustand Abbauen, Resteingabe ε, Keller Z. |
Noch kein Endzustand. Erst der Übergang ε|Z→Z nach Ende schließt den erfolgreichen Lauf ab: akzeptiert. |
abb |
Nach ab liegt nur noch Z im Keller. Der ε-Übergang führt nach Ende, aber ein b ist noch ungelesen. |
Abgelehnt: Ein Endzustand allein genügt nicht. In Ende gibt es keinen Übergang zum Lesen des übrigen b. |
ε |
Die Eingabe ist von Beginn an aufgebraucht; der Keller enthält nur Z. Der Automat bleibt in Sammeln. |
Abgelehnt: Weder die vollständig gelesene Eingabe noch der Kellerboden allein genügen. Sammeln ist kein Endzustand und hat hier keinen passenden Übergang. |
aab |
Die gesamte Eingabe ist gelesen. Der Automat steht in Abbauen, im Keller liegt Za. |
Abgelehnt: Es fehlt ein b. Der Automat erreicht keinen Endzustand, denn der abschließende ε-Übergang ist nur bei oberstem Kellersymbol Z möglich. |
aabb |
Nach dem letzten b liegt nur noch Z im Keller. Der Automat kann mit ε|Z→Z nach Ende wechseln. |
Akzeptiert: Die Eingabe ist vollständig verarbeitet und ein Endzustand erreicht. Der Keller enthält dabei weiterhin Z; er ist also nicht buchstäblich leer. |
Deterministisch und nichtdeterministisch
Bei einem deterministischen Kellerautomaten (DKA) ist in jeder Situation höchstens ein Übergang möglich. Ein ε-Übergang darf dabei nicht mit einem Übergang konkurrieren, der bei gleichem Zustand und Kellersymbol ein Eingabezeichen liest.
Dieser DKA erkennt Wörter der Form wcwR, wobei w ein beliebiges Wort über {a, b} und wR das rückwärts gelesene Wort ist. Beispiele sind c, aca und abcba. Das Zeichen c markiert eindeutig die Mitte.
Im Zustand Speichern wird jedes gelesene a oder b auf den Keller gelegt. Beim Lesen von c wechselt der Automat zu Vergleichen, ohne den Kellerinhalt zu ändern. Danach muss jedes Eingabezeichen zum obersten Kellersymbol passen; dieses wird entfernt. Liegt nur noch Z im Keller, führt ε|Z→Z zum Endzustand.
Bei abcba wächst der Keller zunächst von Z über Za zu Zab. Das c löst den Phasenwechsel aus. Danach werden zuerst b, dann a entfernt. Die Eingabe ist aufgebraucht und der Endzustand wird erreicht.
Warum deterministisch? Das nächste Zeichen bestimmt eindeutig, ob gespeichert oder beim c gewechselt wird. Auch beim Vergleichen ist höchstens ein Übergang möglich. Insbesondere ist ε|Z→Z hier der einzige Übergang für das Kellersymbol Z im Zustand Vergleichen.
Teste außerdem abcab: Trotz gleicher Zeichenanzahlen stimmt die Reihenfolge nicht. abccba wird wegen des zweiten Trennzeichens ebenfalls abgelehnt.
Ein nichtdeterministischer Kellerautomat (NKA) kann mehrere mögliche Übergänge besitzen. Er akzeptiert ein Wort, wenn mindestens ein möglicher Lauf die gesamte Eingabe verarbeitet und in einem Endzustand endet. Nicht jeder Lauf muss erfolgreich sein.
Dieser NKA erkennt Wörter der Form wwR über {a, b}, also Spiegelwörter gerader Länge. Beispiele sind ε, aa, abba und baab. Ein Trennzeichen für die Mitte fehlt.
Der Automat speichert zunächst Zeichen im Keller. Im Zustand Speichern kann er entweder das nächste Eingabezeichen lesen und ablegen oder mit einem ε-Übergang nach Vergleichen wechseln. Für jedes mögliche oberste Kellersymbol gibt es diesen Phasenwechsel. Der NKA berücksichtigt dadurch verschiedene mögliche Positionen der Mitte; er erhält keine Information darüber, welche Position richtig ist.
Bei abba ist der Lauf erfolgreich, der nach ab in die Vergleichsphase wechselt: Im Keller liegt Zab, und die verbleibende Eingabe ba entfernt zuerst b, dann a. Der Endzustand wird bei vollständig gelesener Eingabe erreicht.
Wechselt ein Lauf schon nach dem ersten a, passt das nächste b nicht zum obersten a: Dieser Lauf scheitert. Das Wort wird trotzdem akzeptiert, weil der Wechsel nach ab einen erfolgreichen Lauf liefert.
Warum nichtdeterministisch? Im Zustand Speichern konkurrieren bei gleichem Kellersymbol ein lesender Übergang und der ε-Übergang zum Phasenwechsel. Der Automat betrachtet mehrere mögliche Läufe. Teste abba, abab und aba: Nur das erste dieser drei Wörter gehört zur Sprache. Das leere Wort wird durch zwei ε-Übergänge akzeptiert.