Lektion 2.5

Kellerautomaten

45 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • einen Kellerautomaten mit Zuständen, Eingabe- und Kelleralphabet und Übergängen δ(q,a,A)\delta(q, a, A) lesen und aufschreiben,

  • Akzeptanz durch Endzustand und durch leeren Keller unterscheiden und Läufe als Ablaufprotokoll notieren,

  • Kellerautomaten für {anbn}\{a^n b^n\} 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.

Vermute zuerst

Ein Verfahren für {anbn:n≥0}\{a^n b^n : n \ge 0\}: Unten im Keller liegt ein Markierungszeichen ZZ. Für jedes gelesene a wird ein AA oben auf den Keller gelegt, für jedes b ein AA heruntergenommen. Was liegt im Keller, nachdem aaabaaab gelesen wurde (oberstes Zeichen links)?

Definition

Kellerautomat

Ein Kellerautomat (englisch pushdown automaton, PDA) ist ein Tupel M=(Q,Σ,Γ,δ,q0,Z,F)M = (Q, \Sigma, \Gamma, \delta, q_0, Z, F):

  • QQ: endliche Menge von Zuständen, q0∈Qq_0 \in Q der Startzustand, F⊆QF \subseteq Q die Endzustände,
  • Σ\Sigma: Eingabealphabet,
  • Γ\Gamma: Kelleralphabet, die Zeichen, die im Keller liegen dürfen, mit dem Kellerstartzeichen Z∈ΓZ \in \Gamma,
  • δ\delta: die Übergangsfunktion. Sie ordnet jedem Zustand qq, jedem a∈Σ∪{ε}a \in \Sigma \cup \{\varepsilon\} und jedem A∈ΓA \in \Gamma eine endliche Menge δ(q,a,A)⊆Q×Γ∗\delta(q, a, A) \subseteq Q \times \Gamma^* zu.

(p,γ)∈δ(q,a,A)(p, \gamma) \in \delta(q, a, A) heißt: Steht MM in qq, liegt AA oben im Keller und ist aa das nächste Eingabezeichen, dann darf MM das aa lesen, nach pp wechseln und das AA durch das Wort γ\gamma ersetzen; das erste Zeichen von γ\gamma liegt danach oben. Mit γ=ε\gamma = \varepsilon wird AA nur entfernt, mit γ=BA\gamma = BA wird BB daraufgelegt. Ist a=εa = \varepsilon, liest MM nichts (ε-Übergang). Ohne passenden Übergang bleibt MM stehen.

Eine Konfiguration (q,w,γ)(q, w, \gamma) besteht aus dem Zustand, der Resteingabe und dem Kellerinhalt (oben links). Ein Schritt ist (q,aw,Aβ)⊢(p,w,γβ)(q, aw, A\beta) \vdash (p, w, \gamma\beta) für (p,γ)∈δ(q,a,A)(p, \gamma) \in \delta(q, a, A); ⊢∗\vdash^* heißt „in null oder mehr Schritten“. Wie beim NEA kann es mehrere mögliche Schritte geben.

δ:Q×(Σ∪{ε})×Γ→{endliche Teilmengen von Q×Γ∗}\delta : Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to \{\text{endliche Teilmengen von } Q \times \Gamma^*\}
Definition

Akzeptanz durch Endzustand und durch leeren Keller

MM akzeptiert ww durch Endzustand, wenn es einen Lauf gibt, der die ganze Eingabe liest und in einem Endzustand endet:

L(M)={w∈Σ∗:(q0,w,Z)⊢∗(p,ε,γ) fu¨r ein p∈F und ein γ∈Γ∗}L(M) = \{w \in \Sigma^* : (q_0, w, Z) \vdash^* (p, \varepsilon, \gamma) \text{ für ein } p \in F \text{ und ein } \gamma \in \Gamma^*\}.

MM akzeptiert ww durch leeren Keller, wenn es einen Lauf gibt, der die ganze Eingabe liest und den Keller leert; der Zustand ist dann gleichgültig:

N(M)={w∈Σ∗:(q0,w,Z)⊢∗(p,ε,ε) fu¨r ein p∈Q}N(M) = \{w \in \Sigma^* : (q_0, w, Z) \vdash^* (p, \varepsilon, \varepsilon) \text{ für ein } p \in Q\}.

Bei leerem Keller ist kein Schritt mehr möglich, denn jeder Übergang braucht ein oberstes Kellerzeichen.

Satz

Beide Akzeptanzarten sind gleich mächtig

Zu jedem Kellerautomaten MM gibt es einen Kellerautomaten M′M' mit N(M′)=L(M)N(M') = L(M), und umgekehrt zu jedem MM einen M′M' mit L(M′)=N(M)L(M') = N(M).

Beispiel

Ein Kellerautomat für anbna^n b^n

Q={q0,qa,qb,qf}Q = \{q_0, q_a, q_b, q_f\}, Σ={a,b}\Sigma = \{a, b\}, Γ={Z,A}\Gamma = \{Z, A\}, F={q0,qf}F = \{q_0, q_f\}, Akzeptanz durch Endzustand. Der Zustand qaq_a heißt „ich lese a“, qbq_b heißt „ich lese b“. Alle nicht genannten δ(q,a,A)\delta(q, a, A) sind leer.

ÜbergangBedeutung
δ(q0,a,Z)={(qa,AZ)}\delta(q_0, a, Z) = \{(q_a, AZ)\}erstes a: AA ablegen
δ(qa,a,A)={(qa,AA)}\delta(q_a, a, A) = \{(q_a, AA)\}weiteres a: AA ablegen
δ(qa,b,A)={(qb,ε)}\delta(q_a, b, A) = \{(q_b, \varepsilon)\}erstes b: ein AA entfernen
δ(qb,b,A)={(qb,ε)}\delta(q_b, b, A) = \{(q_b, \varepsilon)\}weiteres b: ein AA entfernen
δ(qb,ε,Z)={(qf,Z)}\delta(q_b, \varepsilon, Z) = \{(q_f, Z)\}alle AA weg: in den Endzustand

Ablaufprotokoll für aabbaabb:

SchrittZustandResteingabeKellerbenutzter Übergang
0q0q_0aabbaabbZZStart
1qaq_aabbabbAZAZδ(q0,a,Z)\delta(q_0, a, Z)
2qaq_abbbbAAZAAZδ(qa,a,A)\delta(q_a, a, A)
3qbq_bbbAZAZδ(qa,b,A)\delta(q_a, b, A)
4qbq_bε\varepsilonZZδ(qb,b,A)\delta(q_b, b, A)
5qfq_fε\varepsilonZZδ(qb,ε,Z)\delta(q_b, \varepsilon, Z)

Die Eingabe ist gelesen und qf∈Fq_f \in F: aabbaabb wird akzeptiert. Das leere Wort wird akzeptiert, weil q0∈Fq_0 \in F.

Zwei abgelehnte Wörter. Bei aabaab endet der Lauf in (qb,ε,AZ)(q_b, \varepsilon, AZ): Kein Übergang passt, und qb∉Fq_b \notin F. Bei abbabb führt der Lauf nach (qb,b,Z)(q_b, b, Z); mit b und ZZ oben gibt es keinen Übergang, nur der ε-Übergang nach (qf,b,Z)(q_f, b, Z) 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.

Kurz geprüft

Der Automat für anbna^n b^n liest aaabbbaaabbb. In welcher Konfiguration steht er, nachdem er aaabaaab gelesen hat?

Beispiel

Palindrome gerader Länge: die Mitte raten

Gesucht ist ein Kellerautomat für {xxR:x∈{a,b}∗}\{x x^R : x \in \{a, b\}^*\}; dabei ist xRx^R das Wort xx 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.

Q={q0,q1,q2}Q = \{q_0, q_1, q_2\}, Γ={Z,A,B}\Gamma = \{Z, A, B\}, F={q2}F = \{q_2\}. Für jedes X∈ΓX \in \Gamma:

  • δ(q0,a,X)∋(q0,AX)\delta(q_0, a, X) \ni (q_0, AX) und δ(q0,b,X)∋(q0,BX)\delta(q_0, b, X) \ni (q_0, BX): erste Hälfte ablegen,
  • δ(q0,ε,X)∋(q1,X)\delta(q_0, \varepsilon, X) \ni (q_1, X): hier ist die Mitte (geraten),
  • δ(q1,a,A)={(q1,ε)}\delta(q_1, a, A) = \{(q_1, \varepsilon)\} und δ(q1,b,B)={(q1,ε)}\delta(q_1, b, B) = \{(q_1, \varepsilon)\}: vergleichen,
  • δ(q1,ε,Z)={(q2,Z)}\delta(q_1, \varepsilon, Z) = \{(q_2, Z)\}: alles verglichen, akzeptieren.

Der akzeptierende Lauf für abbaabba:

SchrittZustandResteingabeKellerbenutzter Übergang
0q0q_0abbaabbaZZStart
1q0q_0bbabbaAZAZδ(q0,a,Z)\delta(q_0, a, Z)
2q0q_0babaBAZBAZδ(q0,b,A)\delta(q_0, b, A)
3q1q_1babaBAZBAZδ(q0,ε,B)\delta(q_0, \varepsilon, B), Mitte geraten
4q1q_1aaAZAZδ(q1,b,B)\delta(q_1, b, B)
5q1q_1ε\varepsilonZZδ(q1,a,A)\delta(q_1, a, A)
6q2q_2ε\varepsilonZZδ(q1,ε,Z)\delta(q_1, \varepsilon, Z)

Die anderen Läufe raten die Mitte falsch. Nach 00 Zeichen: Der Automat geht nach q2q_2, aber abbaabba bleibt ungelesen. Nach 11 Zeichen: In (q1,bba,AZ)(q_1, bba, AZ) passt b nicht zu AA. Nach 33 Zeichen: In (q1,a,BBAZ)(q_1, a, BBAZ) passt a nicht zu BB. Nach 44 Zeichen: In (q1,ε,ABBAZ)(q_1, \varepsilon, ABBAZ) ist kein Schritt mehr möglich. Ein akzeptierender Lauf genügt, also wird abbaabba akzeptiert.

Häufige Fehler

Ein Lauf scheitert, also abgelehnt

„Beim Raten der Mitte nach dem ersten Zeichen bleibt der Automat bei abbaabba stecken. Also akzeptiert er abbaabba nicht.“ Ebenso falsch: „Der Automat war in einem Endzustand, also ist das Wort akzeptiert“, obwohl noch Eingabe übrig war.

Richtig ist

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: (p,ε,γ)(p, \varepsilon, \gamma) mit p∈Fp \in F beziehungsweise (p,ε,ε)(p, \varepsilon, \varepsilon).

Definition

Deterministischer Kellerautomat

Ein Kellerautomat heißt deterministisch (DPDA), wenn in jeder Konfiguration höchstens ein Schritt möglich ist. Genauer gilt für alle q∈Qq \in Q und A∈ΓA \in \Gamma:

  • δ(q,a,A)\delta(q, a, A) hat für jedes a∈Σ∪{ε}a \in \Sigma \cup \{\varepsilon\} höchstens ein Element,
  • ist δ(q,ε,A)≠∅\delta(q, \varepsilon, A) \ne \emptyset, dann ist δ(q,a,A)=∅\delta(q, a, A) = \emptyset für alle a∈Σa \in \Sigma.

Eine Sprache heißt deterministisch kontextfrei, wenn ein DPDA sie durch Endzustand akzeptiert. Der Automat für anbna^n b^n oben ist deterministisch: Der einzige ε-Übergang benutzt (qb,Z)(q_b, Z), und dafür gibt es keinen Übergang mit einem Eingabezeichen. Der Palindrom-Automat ist es nicht, denn in q0q_0 gibt es zu jedem Kellerzeichen sowohl Lese- als auch ε-Übergänge.

Satz

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.

Satz

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 G=(V,Σ,P,S)G = (V, \Sigma, P, S) nimm einen Automaten mit einem einzigen Zustand qq, Kelleralphabet Γ=V∪Σ\Gamma = V \cup \Sigma, Kellerstartzeichen SS, Akzeptanz durch leeren Keller und diesen Übergängen:

  • für jede Regel A→αA \to \alpha: (q,α)∈δ(q,ε,A)(q, \alpha) \in \delta(q, \varepsilon, A) (Variable oben: eine Regel raten und anwenden),
  • für jedes a∈Σa \in \Sigma: δ(q,a,a)={(q,ε)}\delta(q, a, a) = \{(q, \varepsilon)\} (Terminal oben: mit der Eingabe vergleichen).
Beispiel

Von S→aSb∣εS \to aSb \mid \varepsilon zum Kellerautomaten

Übergänge: δ(q,ε,S)={(q,aSb),(q,ε)}\delta(q, \varepsilon, S) = \{(q, aSb), (q, \varepsilon)\}, δ(q,a,a)={(q,ε)}\delta(q, a, a) = \{(q, \varepsilon)\}, δ(q,b,b)={(q,ε)}\delta(q, b, b) = \{(q, \varepsilon)\}. Der akzeptierende Lauf für aabbaabb:

SchrittZustandResteingabeKellerbenutzter Übergang
0qqaabbaabbSSStart
1qqaabbaabbaSbaSbS→aSbS \to aSb
2qqabbabbSbSba vergleichen
3qqabbabbaSbbaSbbS→aSbS \to aSb
4qqbbbbSbbSbba vergleichen
5qqbbbbbbbbS→εS \to \varepsilon
6qqbbbbb vergleichen
7qqε\varepsilonε\varepsilonb vergleichen

Liest man in jeder Zeile den schon gelesenen Teil und dahinter den Keller, erhält man SS, aSbaSb, aaSbbaaSbb, aabbaabb: genau die Linksableitung. In den Schritten 1, 3 und 5 musste der Automat die richtige Regel raten.

Kurz geprüft

Welche Sprache ist deterministisch kontextfrei?

Zusammenfassung

  • Ein Kellerautomat (Q,Σ,Γ,δ,q0,Z,F)(Q, \Sigma, \Gamma, \delta, q_0, Z, F) ist ein endlicher Automat mit Keller; ein Übergang (p,γ)∈δ(q,a,A)(p, \gamma) \in \delta(q, a, A) liest aa oder nichts und ersetzt das oberste Kellerzeichen AA durch γ\gamma.

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

  • {anbn}\{a^n b^n\} 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

Aufgabe 1Numerisch

Wie viele Schritte macht der Kellerautomat für anbna^n b^n aus der Lektion auf dem Wort aaabbbaaabbb, bis er im Endzustand qfq_f steht?

Aufgabe 2Multiple Choice

Ein Kellerautomat steht in (q,ab,AZ)(q, ab, AZ) und hat den Übergang (p,BBA)∈δ(q,a,A)(p, BBA) \in \delta(q, a, A). Welche Konfiguration erreicht er damit?

Aufgabe 3Multiple Choice

Der Palindrom-Automat aus der Lektion liest aaaaaaaa. Nach wie vielen gelesenen Zeichen muss er die Mitte raten, damit der Lauf akzeptiert?

Aufgabe 4Freitext

Gib einen Kellerautomaten an, der {anb2n:n≥0}\{a^n b^{2n} : n \ge 0\} durch Endzustand akzeptiert, und schreibe das Ablaufprotokoll für abbabb auf.

Aufgabe 5Freitext

Konstruiere zur Grammatik S→aSa∣bSb∣a∣b∣εS \to aSa \mid bSb \mid a \mid b \mid \varepsilon (alle Palindrome) den Kellerautomaten mit einem Zustand und schreibe einen akzeptierenden Lauf für abaaba als Ablaufprotokoll.

Aufgabe 6Freitext

Gib einen Kellerautomaten für {x∈{a,b}∗:x entha¨lt gleich viele a wie b}\{x \in \{a, b\}^* : x \text{ enthält gleich viele a wie b}\} an. Erkläre, was der Keller speichert, und prüfe deinen Automaten am Wort abbaabba.