MINT üben

Der Kellerautomat

Ein Stapel als Gedächtnis — und plötzlich kann ein Automat beliebig weit zählen.

1

Ein Automat mit Keller

Einem DEA fehlt ein Speicher, der mitwächst. Der Kellerautomat bekommt deshalb einen Stapel dazu — den Keller.

  • Keller:Stapelspeicher ohne Größengrenze — nur das oberste Zeichen ist sichtbar (wie beim Stack: push, pop).
  • Kelleralphabet Γ:Zeichen, die im Keller liegen dürfen, z. B. \(\Gamma=\{\texttt{A},\,\#\}\).
  • Vorbelegung #:liegt beim Start allein im Keller und markiert den Kellerboden.
  • Übergang:(X,e):W — oberstes Kellerzeichen X, Eingabezeichen e; X wird entfernt, W abgelegt.
  • Ablegen:das rechte Zeichen von W zuerst — bei A# liegt danach A oben.
  • ε-Übergang:(X,ε):W — Zustandswechsel, ohne ein Zeichen zu lesen.
  • Akzeptieren:Wort vollständig gelesen und Endzustand erreicht. Passt kein Übergang, bleibt der Automat stecken: abgelehnt.

Der Automat soll \(L=\{a^nb^n\mid n\ge 0\}\) erkennen. Wähle ein Beispiel oder tippe ein eigenes Wort (Knöpfe oder Tasten a, b, ⌫ auf der Bühne) und lass ihn mit ▶ oder „Ein Schritt“ arbeiten. Achte darauf, was oben auf dem Keller passiert.

Kellerautomat für aⁿbⁿ

SchrittZustandResteingabeKeller (oben links)Übergang

Halte fest: Jedes a legt ein A ab, jedes b nimmt eins weg. Der Keller merkt sich die Anzahl der a, egal wie groß sie ist. Liegt am Ende wieder # oben, stimmen die Anzahlen.

Merke

Kellerautomat: Endlicher Automat mit einem Keller (Stapel ohne Größengrenze), von dem nur das oberste Zeichen sichtbar ist; er enthält anfangs nur #.

Übergang: \((X,e):W\) entfernt das oberste Kellerzeichen \(X\), liest \(e\) und legt \(W\) ab, das rechte Zeichen zuerst; bei ε wird nichts gelesen.

Akzeptieren: Das Wort ist vollständig gelesen und ein Endzustand erreicht; passt kein Übergang, wird abgelehnt.

2

Konfigurationen und Akzeptanz

Den Lauf eines Kellerautomaten schreibt man als Folge von Konfigurationen auf.

  • Konfiguration:(Zustand, Resteingabe, Kellerinhalt), Kellerinhalt oben links.
  • Startkonfiguration:(Startzustand, ganzes Wort, #).
  • NKA:Kellerautomaten dürfen nichtdeterministisch sein — ein Wort gilt als akzeptiert, wenn mindestens ein Lauf im Endzustand endet.
  • Mehr als ein DEA:\(a^nb^n\), Klammerausdrücke, Palindrome — mit Keller erkennbar.

Herleitung:

\((\text{z0},\ \texttt{aabb},\ \texttt{\#})\)
Start
Startkonfiguration: Zustand z0, das ganze Wort ist ungelesen, im Keller liegt nur #.
\((\text{z1},\ \texttt{abb},\ \texttt{A\#})\)
(#,a):A#
# oben, a gelesen: # wird entfernt, A# abgelegt — erst #, dann A. Oben liegt A.
\((\text{z1},\ \texttt{bb},\ \texttt{AA\#})\)
(A,a):AA
Jedes weitere a legt ein zusätzliches A ab. Der Keller zählt die a.
\((\text{z2},\ \texttt{b},\ \texttt{A\#})\)
(A,b):ε
Das erste b entfernt ein A und legt nichts zurück. Der Automat wechselt in die b-Phase.
\((\text{z2},\ \varepsilon,\ \texttt{\#})\)
(A,b):ε
Das zweite b entfernt das letzte A. Oben liegt wieder # — genau so viele b wie a.
\((\text{z3},\ \varepsilon,\ \texttt{\#})\)
(#,ε):#
Ohne ein Zeichen zu lesen, prüft der ε-Übergang „oben liegt #“ und führt in den Endzustand z3. Eingabe vollständig gelesen, Endzustand erreicht: aabb wird akzeptiert.
Merke

Kellerautomat (NKA): Er darf nichtdeterministisch sein: Ein Wort wird akzeptiert, wenn mindestens ein Lauf nach dem vollständigen Lesen im Endzustand endet.

Konfiguration: (Zustand, Resteingabe, Kellerinhalt) mit Kellerinhalt oben links; Start ist (Startzustand, ganzes Wort, #).

Leistung: Mit Keller erkennbar: \(a^nb^n\), Klammerausdrücke, Palindrome.

3

Allgemeine Hinweise

Oben steht links

(A,a):BA legt erst A, dann B ab — B liegt oben. Schreibe den Kellerinhalt immer mit dem obersten Zeichen links.

X wird immer entfernt

Soll X liegen bleiben, muss es in W wieder vorkommen: (#,ε):# prüft nur „oben liegt #“ und lässt den Keller unverändert.

Endzustand zählt, nicht der Keller

Ein leerer Keller allein akzeptiert nicht. Entscheidend ist: Wort vollständig gelesen und Endzustand erreicht.

Videos