MINT lernen

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 (9.2.2). 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.

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): endlicher Automat mit einem Keller, der anfangs nur # enthält. Ein Übergang (X,e):W entfernt das oberste Kellerzeichen X, liest e (bei ε nichts) und legt W ab — das rechte Zeichen zuerst. Ein Wort wird akzeptiert, wenn es einen Lauf gibt, der nach dem vollständigen Lesen in einem Endzustand endet.

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