Kellerautomaten
Lesen anpassen
Nach dieser Lektion kannst du
einen Kellerautomaten mit Zuständen, Eingabe- und Kelleralphabet und Übergängen lesen und aufschreiben,
Akzeptanz durch Endzustand und durch leeren Keller unterscheiden und Läufe als Ablaufprotokoll notieren,
Kellerautomaten für und für Palindrome gerader Länge entwerfen,
begründen, warum Nichtdeterminismus bei Kellerautomaten echt stärker ist als Determinismus,
aus einer kontextfreien Grammatik einen Kellerautomaten konstruieren und den Zusammenhang mit Parsern erklären.
Vorausgesetzt: Nichtdeterministische Automaten und die Potenzmengenkonstruktion, Kontextfreie Grammatiken und Ableitungsbäume
Wie prüft ein Texteditor, ob die Klammern in einem Programm zusammenpassen? Er legt jede öffnende Klammer auf einen Stapel und nimmt bei jeder schließenden die oberste wieder herunter. Passt sie nicht oder ist der Stapel leer, meldet er einen Fehler. Ein endlicher Automat kann das nicht, weil er beliebig viele offene Klammern zählen müsste. Mit einem Stapel geht es mühelos.
Ein Kellerautomat ist genau das: ein endlicher Automat mit einem unbegrenzt großen Stapel, dem Keller, auf den er nur von oben zugreifen kann. Dieses Modell erkennt genau die kontextfreien Sprachen, und es ist das Rechenmodell hinter den Parsern in Compilern.
Ein Verfahren für : Unten im Keller liegt ein Markierungszeichen . Für jedes gelesene a wird ein oben auf den Keller gelegt, für jedes b ein heruntergenommen. Was liegt im Keller, nachdem gelesen wurde (oberstes Zeichen links)?
Kellerautomat
Ein Kellerautomat (englisch pushdown automaton, PDA) ist ein Tupel :
- : endliche Menge von Zuständen, der Startzustand, die Endzustände,
- : Eingabealphabet,
- : Kelleralphabet, die Zeichen, die im Keller liegen dürfen, mit dem Kellerstartzeichen ,
- : die Übergangsfunktion. Sie ordnet jedem Zustand , jedem und jedem eine endliche Menge zu.
heißt: Steht in , liegt oben im Keller und ist das nächste Eingabezeichen, dann darf das lesen, nach wechseln und das durch das Wort ersetzen; das erste Zeichen von liegt danach oben. Mit wird nur entfernt, mit wird daraufgelegt. Ist , liest nichts (ε-Übergang). Ohne passenden Übergang bleibt stehen.
Eine Konfiguration besteht aus dem Zustand, der Resteingabe und dem Kellerinhalt (oben links). Ein Schritt ist für ; heißt „in null oder mehr Schritten“. Wie beim NEA kann es mehrere mögliche Schritte geben.
Akzeptanz durch Endzustand und durch leeren Keller
akzeptiert durch Endzustand, wenn es einen Lauf gibt, der die ganze Eingabe liest und in einem Endzustand endet:
.
akzeptiert durch leeren Keller, wenn es einen Lauf gibt, der die ganze Eingabe liest und den Keller leert; der Zustand ist dann gleichgültig:
.
Bei leerem Keller ist kein Schritt mehr möglich, denn jeder Übergang braucht ein oberstes Kellerzeichen.
Beide Akzeptanzarten sind gleich mächtig
Zu jedem Kellerautomaten gibt es einen Kellerautomaten mit , und umgekehrt zu jedem einen mit .
Beweisidee: In beiden Richtungen bekommt ein neues unterstes Kellerzeichen und legt zuerst mit einem ε-Übergang darauf; dann simuliert er .
Von Endzustand zu leerem Keller: Aus jedem Endzustand von darf per ε-Übergang in einen neuen Zustand wechseln, der den Keller ganz leert, auch . Das verhindert, dass akzeptiert, wenn seinen Keller außerhalb eines Endzustands leert.
Von leerem Keller zu Endzustand: Sieht oben , hat seinen Keller gerade geleert. Dann wechselt per ε-Übergang in einen neuen Endzustand.
Ein Kellerautomat für
Ein Kellerautomat für
, , , , Akzeptanz durch Endzustand. Der Zustand heißt „ich lese a“, heißt „ich lese b“. Alle nicht genannten sind leer.
| Übergang | Bedeutung |
|---|---|
| erstes a: ablegen | |
| weiteres a: ablegen | |
| erstes b: ein entfernen | |
| weiteres b: ein entfernen | |
| alle weg: in den Endzustand |
Ablaufprotokoll für :
| Schritt | Zustand | Resteingabe | Keller | benutzter Übergang |
|---|---|---|---|---|
| 0 | Start | |||
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 |
Die Eingabe ist gelesen und : wird akzeptiert. Das leere Wort wird akzeptiert, weil .
Zwei abgelehnte Wörter. Bei endet der Lauf in : Kein Übergang passt, und . Bei führt der Lauf nach ; mit b und oben gibt es keinen Übergang, nur der ε-Übergang nach ist möglich, und dort bleibt der Automat stehen. Er steht zwar in einem Endzustand, hat aber die Eingabe nicht zu Ende gelesen, also zählt das nicht.
Der Automat für liest . In welcher Konfiguration steht er, nachdem er gelesen hat?
Palindrome gerader Länge: die Mitte raten
Palindrome gerader Länge: die Mitte raten
Gesucht ist ein Kellerautomat für ; dabei ist das Wort rückwärts. Die Idee: Die erste Hälfte auf den Keller legen und die zweite Hälfte mit dem Keller vergleichen, der sie in umgekehrter Reihenfolge herausgibt. Wo die Mitte ist, weiß der Automat nicht; er rät sie mit einem ε-Übergang.
, , . Für jedes :
- und : erste Hälfte ablegen,
- : hier ist die Mitte (geraten),
- und : vergleichen,
- : alles verglichen, akzeptieren.
Der akzeptierende Lauf für :
| Schritt | Zustand | Resteingabe | Keller | benutzter Übergang |
|---|---|---|---|---|
| 0 | Start | |||
| 1 | ||||
| 2 | ||||
| 3 | , Mitte geraten | |||
| 4 | ||||
| 5 | ||||
| 6 |
Die anderen Läufe raten die Mitte falsch. Nach Zeichen: Der Automat geht nach , aber bleibt ungelesen. Nach Zeichen: In passt b nicht zu . Nach Zeichen: In passt a nicht zu . Nach Zeichen: In ist kein Schritt mehr möglich. Ein akzeptierender Lauf genügt, also wird akzeptiert.
Ein Lauf scheitert, also abgelehnt
Ein Lauf scheitert, also abgelehnt
„Beim Raten der Mitte nach dem ersten Zeichen bleibt der Automat bei stecken. Also akzeptiert er nicht.“ Ebenso falsch: „Der Automat war in einem Endzustand, also ist das Wort akzeptiert“, obwohl noch Eingabe übrig war.
Ein nichtdeterministischer Kellerautomat akzeptiert, wenn mindestens ein Lauf akzeptiert, wie beim NEA. Und akzeptiert wird nur in einer Konfiguration, in der die Eingabe vollständig gelesen ist: mit beziehungsweise .
Deterministischer Kellerautomat
Ein Kellerautomat heißt deterministisch (DPDA), wenn in jeder Konfiguration höchstens ein Schritt möglich ist. Genauer gilt für alle und :
- hat für jedes höchstens ein Element,
- ist , dann ist für alle .
Eine Sprache heißt deterministisch kontextfrei, wenn ein DPDA sie durch Endzustand akzeptiert. Der Automat für oben ist deterministisch: Der einzige ε-Übergang benutzt , und dafür gibt es keinen Übergang mit einem Eingabezeichen. Der Palindrom-Automat ist es nicht, denn in gibt es zu jedem Kellerzeichen sowohl Lese- als auch ε-Übergänge.
Nichtdeterminismus ist echt stärker
Jede deterministisch kontextfreie Sprache ist kontextfrei, aber nicht umgekehrt. Anders als bei endlichen Automaten lässt sich Nichtdeterminismus also nicht wegkonstruieren.
Wir benutzen einen Satz, den wir hier ohne Beweis übernehmen: Das Komplement einer deterministisch kontextfreien Sprache ist wieder deterministisch kontextfrei. (Die Idee ist, End- und Nicht-Endzustände zu vertauschen; die Schwierigkeit liegt bei Läufen, die stehen bleiben oder endlos ε-Übergänge machen.)
Sei und . Ein Wort liegt genau dann in , wenn es nicht die Form hat (eine reguläre Sprache) oder wenn es die Form mit oder mit hat. Für ist zum Beispiel , , , , eine kontextfreie Grammatik, für geht es genauso. Eine Vereinigung kontextfreier Sprachen ist kontextfrei (neues Startsymbol mit einer Regel zu jedem Teil), also ist kontextfrei.
Wäre deterministisch kontextfrei, dann auch sein Komplement , und damit wäre kontextfrei. Nach dem Pumping-Lemma für kontextfreie Sprachen ist aber nicht kontextfrei. Also ist kontextfrei, aber nicht deterministisch kontextfrei.
Kellerautomaten und kontextfreie Grammatiken
Eine Sprache ist genau dann kontextfrei, wenn ein Kellerautomat sie akzeptiert.
Die Richtung von der Grammatik zum Automaten ist eine einfache Konstruktion. Zu nimm einen Automaten mit einem einzigen Zustand , Kelleralphabet , Kellerstartzeichen , Akzeptanz durch leeren Keller und diesen Übergängen:
- für jede Regel : (Variable oben: eine Regel raten und anwenden),
- für jedes : (Terminal oben: mit der Eingabe vergleichen).
Beweisidee: Der Automat führt eine Linksableitung durch. Zu jedem Zeitpunkt gilt: gelesener Teil der Eingabe, gefolgt vom Kellerinhalt, ist eine Satzform der Linksableitung. Liegt eine Variable oben, ist sie die am weitesten links stehende, die noch nicht ersetzt wurde, und der Automat ersetzt sie. Liegt ein Terminal oben, muss es mit dem nächsten Eingabezeichen übereinstimmen. Mit Induktion über die Zahl der Schritte folgt: mit einer Linksableitung genau dann, wenn .
Die Gegenrichtung (vom Automaten zur Grammatik) baut Variablen für „der Automat geht von nach und baut dabei das oben im Keller ab“; sie ist aufwendiger, und wir lassen sie hier weg.
Von zum Kellerautomaten
Von zum Kellerautomaten
Übergänge: , , . Der akzeptierende Lauf für :
| Schritt | Zustand | Resteingabe | Keller | benutzter Übergang |
|---|---|---|---|---|
| 0 | Start | |||
| 1 | ||||
| 2 | a vergleichen | |||
| 3 | ||||
| 4 | a vergleichen | |||
| 5 | ||||
| 6 | b vergleichen | |||
| 7 | b vergleichen |
Liest man in jeder Zeile den schon gelesenen Teil und dahinter den Keller, erhält man , , , : genau die Linksableitung. In den Schritten 1, 3 und 5 musste der Automat die richtige Regel raten.
Welche Sprache ist deterministisch kontextfrei?
Zusammenfassung
Ein Kellerautomat ist ein endlicher Automat mit Keller; ein Übergang liest oder nichts und ersetzt das oberste Kellerzeichen durch .
Akzeptanz durch Endzustand oder durch leeren Keller; in beiden Fällen muss die Eingabe ganz gelesen sein, und beide Arten sind gleich mächtig.
Ein Ablaufprotokoll notiert Schritt, Zustand, Resteingabe und Keller.
hat einen deterministischen Kellerautomaten; für Palindrome gerader Länge wird die Mitte nichtdeterministisch geraten.
Deterministisch kontextfreie Sprachen sind eine echte Teilklasse der kontextfreien Sprachen.
Kellerautomaten akzeptieren genau die kontextfreien Sprachen; aus einer Grammatik entsteht ein Automat mit einem Zustand, der eine Linksableitung simuliert.
LL- und LR-Parser sind deterministische Kellerautomaten und arbeiten in linearer Zeit.
Übungen
Wie viele Schritte macht der Kellerautomat für aus der Lektion auf dem Wort , bis er im Endzustand steht?
Ein Kellerautomat steht in und hat den Übergang . Welche Konfiguration erreicht er damit?
Der Palindrom-Automat aus der Lektion liest . Nach wie vielen gelesenen Zeichen muss er die Mitte raten, damit der Lauf akzeptiert?
Gib einen Kellerautomaten an, der durch Endzustand akzeptiert, und schreibe das Ablaufprotokoll für auf.
Konstruiere zur Grammatik (alle Palindrome) den Kellerautomaten mit einem Zustand und schreibe einen akzeptierenden Lauf für als Ablaufprotokoll.
Gib einen Kellerautomaten für an. Erkläre, was der Keller speichert, und prüfe deinen Automaten am Wort .