Kellerautomaten entwickeln

Vom Kellerplan zum Automaten

Einen Kellerautomaten entwirfst du vom Keller her: Erst festlegen, was gespeichert wird — dann ergeben sich die Übergänge fast von selbst.

Merken:Was muss der Automat über den gelesenen Anfang wissen — und wie viel davon?
Kellerplan:Welche Eingabe legt welches Zeichen ab, welche entfernt eines?
Phasen:je Abschnitt des Worts ein Zustand, z. B. „a lesen“, „b lesen“, „fertig“.
Übergänge:je Zustand jedes mögliche oberste Kellerzeichen mit jedem Eingabezeichen durchgehen.
Abschluss:(#,ε):# in einen Endzustand prüft „Keller wieder leer“.
Testen:Wörter aus L, Randfälle wie ε und Wörter knapp daneben.

Zustand	oben	gelesen	Übergang	Idee
z0	#	a	(#,a):AA# → z1	je a zwei A ablegen
z1	A	a	(A,a):AAA	A zurück, zwei A dazu
z1	A	b	(A,b):ε → z2	erstes b: ein A weg, b-Phase
z2	A	b	(A,b):ε	je b ein A weg
z2	#	ε	(#,ε):# → z3	Keller leer: fertig

Kellerplan als Automat: \(L=\{a^nb^{2n}\mid n\ge 0\}\) (z0 und z3 Endzustände)

Drei Entwürfe sollen \(L=\{w\in\{a,b\}^*\mid w \text{ enthält gleich viele a wie b}\}\) erkennen. Wähle zwei davon, lege ihre Kellerhöhen übereinander und decke den Lauf mit ▶ Zeichen für Zeichen auf. Wechsle das Wort, bis du bei jedem fehlerhaften Entwurf ein falsch behandeltes Wort gefunden hast.

Entwurf blau

Entwurf orange

Wort

Halte fest: Der richtige Entwurf speichert den Überschuss — lauter A, wenn mehr a gelesen wurden, lauter B bei mehr b. Seine Kellerhöhe folgt genau der gestrichelten Soll-Kurve. Wer nur eine Richtung zählt, bleibt stecken; wer den Endzustand ohne (#,ε):# erreicht, akzeptiert zu viel.

Die Mitte raten

Manchmal weiß der Automat nicht, wann er von „ablegen“ auf „vergleichen“ umschalten muss. Dann darf er raten.

\(w^R\):das Wort w rückwärts, z. B. \((\texttt{abb})^R=\texttt{bba}\).
Mit Mittelmarke:\(\{w\,c\,w^R\}\) — das c zeigt den Wechsel an; jeder Schritt ist eindeutig.
Ohne Marke:\(\{w\,w^R\}\) — die ε-Übergänge (A,ε):A und (B,ε):B raten die Mitte.
Raten erlaubt:Ein NKA akzeptiert, wenn eine Rate-Möglichkeit im Endzustand endet; falsch geratene Läufe bleiben stecken.
Grenze:\(\{a^nb^nc^n\}\) verlangt zwei Vergleiche mit derselben Anzahl — dafür reicht ein Keller nicht.

NKA für \(\{w\,w^R\mid w\in\{a,b\}^*\}\) (z0 und z3 Endzustände)

Herleitung:

\((\text{z0},\ \texttt{abba},\ \texttt{\#})\)

Start

Das ganze Wort ist ungelesen, im Keller liegt #.

\((\text{z1},\ \texttt{bba},\ \texttt{A\#})\)

(#,a):A#

Erste Hälfte: Jedes gelesene Zeichen wird als Großbuchstabe abgelegt.

\((\text{z1},\ \texttt{ba},\ \texttt{BA\#})\)

(A,b):BA

A bleibt liegen, B kommt oben drauf. Der Keller enthält die erste Hälfte rückwärts.

\((\text{z2},\ \texttt{ba},\ \texttt{BA\#})\)

(B,ε):B

Geraten: Hier ist die Mitte. Der ε-Übergang wechselt die Phase, ohne zu lesen.

\((\text{z2},\ \texttt{a},\ \texttt{A\#})\)

(B,b):ε

Zweite Hälfte: Das gelesene b passt zum obersten B — entfernen.

\((\text{z2},\ \varepsilon,\ \texttt{\#})\)

(A,a):ε

Auch a passt zu A. Oben liegt wieder #.

\((\text{z3},\ \varepsilon,\ \texttt{\#})\)

(#,ε):#

Endzustand nach vollständigem Lesen: abba wird akzeptiert. Hätte der Automat die Mitte an anderer Stelle geraten, wäre dieser Lauf stecken geblieben — für die Akzeptanz genügt ein passender Lauf.

Merke

Kellerautomaten entwickeln: Kellerplan festlegen (was wird abgelegt, was entfernt) → je Phase ein Zustand → Übergänge (X,e):W für jedes benötigte Paar aus oberstem Kellerzeichen und Eingabe → mit (#,ε):# in den Endzustand. Ist ein Wechsel im Wort nicht markiert, rät ein ε-Übergang ihn (NKA).

Allgemeine Hinweise

Jedes oberste Zeichen bedenken

Fehlt (#,b):B#, bleibt der Automat bei ba sofort stecken. Gehe je Zustand alle Paare aus Kellerzeichen und Eingabe durch.

Endzustand erst nach der Prüfung

Führt der Weg ohne (#,ε):# in den Endzustand, werden auch Wörter mit Rest im Keller akzeptiert.

Mit Randfällen testen

Teste ε, Wörter aus einem Zeichen, die falsche Reihenfolge und ein Zeichen zu viel — dort stecken die meisten Entwurfsfehler.