Qualifikationsphase

Q3.3 · Kellerautomat

Endliche Automaten mit LIFO-Speicher für geschachtelte und kontextfreie Strukturen

Q3.2 hat endliche Automaten als Erkenner regulärer Sprachen eingeführt: Ihre gesamte Speicherung liegt im aktuellen Zustand. Weil es nur endlich viele Zustände gibt, lassen sich unbeschränkte Zählung und beliebig tiefe Schachtelung damit nicht allgemein festhalten.

Q3.3 fragt deshalb, was passiert, wenn ein Automat zusätzlich einen Keller oder Stack erhält. Ein Kellerautomat ersetzt den endlichen Automaten nicht, sondern erweitert ihn um einen LIFO-Speicher. Er liest weiterhin ein Eingabewort und wechselt Zustände; jeder Schritt kann aber zusätzlich vom obersten Kellerzeichen abhängen und den Keller verändern.

Damit schließt Q3.3 auch an Q3.1 an: Was kontextfreie Grammatiken erzeugend beschreiben, können Kellerautomaten in der allgemeinen nichtdeterministischen Form erkennend prüfen. Im Mittelpunkt stehen Klammerausdrücke, Stackoperationen, Konfigurationen, a^n b^n, Nichtdeterminismus und die Grenzen eines einzelnen Stacks.

Orientierung: Warum braucht man einen Kellerautomaten?
Grenzen endlicher Automaten und Idee des Stacks

Grenze endlicher Automaten

nur endlich viele Zustände
Speicherung nur im aktuellen Zustand
keine beliebig tiefe Schachtelung speicherbar
kein unbeschränkter Anzahlvergleich für beliebiges n
Grenzfälle: Klammerausdrücke und a^n b^n

Idee des Kellerautomaten

endlicher Automat plus genau ein Stack
merkt sich Symbole in einer Stapelstruktur
liest jeweils nur das oberste Kellerzeichen
kann Symbole ablegen, entfernen oder ersetzen
kein beliebiges Gedächtnis, sondern strikt LIFO

Leitidee

Bei einem DEA oder NEA hängt der nächste Schritt von Zustand und Eingabesymbol ab. Beim Kellerautomaten kommt die Kelleroberseite hinzu: Zustand, Eingabesymbol oder ε und oberstes Kellerzeichen bestimmen gemeinsam den nächsten Schritt.

Klammerausdrücke als Einstieg
Geschachtelte Strukturen benötigen Speicher

Programmiersprachen verwenden Klammern für echte Schachtelung: Blöcke, Ausdrücke und Funktionsaufrufe können ineinander liegen. Während des Lesens muss deshalb gespeichert werden, welche öffnenden Klammern noch auf ihre passende schließende Klammer warten.

Das LIFO-Prinzip passt genau zu dieser Prüfung. Jede öffnende Klammer wird gemerkt; jede schließende Klammer muss zur zuletzt geöffneten Klammer passen. Im Automaten-/Formalsprachen-Werkzeug zeigt das Preset pda-parentheses diese Idee: Jede ( führt zu einem Push, jede passende ) zu einem Pop.

Trace für das Eingabewort (()) mit Push und Pop im Stack — Was man sieht: Konfigurationen für `(())` mit Stackentwicklung. Begriff: Push/Pop auf dem Keller. Lernpunkt: Gültig nur, wenn nie ohne passenden Marker gepoppt wird und am Ende kein offener Marker übrig bleibt.

Beispiele und Werkzeugbezug

gültig: (), (()), ()()
ungültig: ((), ()), )(

Im Automaten-/Formalsprachen-Werkzeug: Bereich Kellerautomat / Speicherautomat aufklappen, Preset pda-parentheses laden, Eingabewort eingeben, dann mit Schritt oder Komplett ausführen den Trace und die Stack-Anzeige auswerten.

Aufbau eines Kellerautomaten
Bestandteile und formale Beschreibung

Ein Kellerautomat bleibt zustandsbasiert, wird aber formal um ein Kelleralphabet, ein Kellerbodensymbol und eine Übergangsfunktion mit Kellerbezug erweitert.

Formale Beschreibung als 7-Tupel

K = (Q, Σ, Γ, δ, q₀, #, F)

Q: endliche Zustandsmenge
Σ: Eingabealphabet
Γ: Kelleralphabet
δ: Übergangsfunktion
q₀: Startzustand
#: Kellerstartsymbol / Kellerbodensymbol
F: Menge der akzeptierenden Endzustände

In der allgemeinen nichtdeterministischen Form betrachtet die Übergangsfunktion den aktuellen Zustand, ein Eingabesymbol oder ε und das oberste Kellerzeichen. Zu einer solchen Situation kann sie mehrere mögliche Folgeschritte liefern. Jeder Folgeschritt beschreibt einen Folgezustand und einen Kellerersatz: die Symbolfolge, die das bisherige Kellerzeichen ersetzt.

Abiturrelevant ist außerdem die Sicht auf Konfigurationen: Eine Konfiguration besteht aus aktuellem Zustand, Restwort und Kellerinhalt. Genau diese Dreier-Sicht wird im Werkzeugtrace sichtbar.

Der Keller / Stack
LIFO-Prinzip und typische Operationen

Der Keller ist ein Speicher mit LIFO-Prinzip: zuletzt abgelegt, zuerst gelesen. Gelesen wird immer nur das oberste Kellerzeichen. Genau dadurch eignet sich der Stack für Rückkehr- und Schachtelungsmuster, aber nicht als frei durchsuchbares Gedächtnis.

push: Symbol auf den Keller legen
pop: oberstes Symbol entfernen
replace: oberstes Symbol durch eine Symbolfolge ersetzen
ε als Eingabe: Es wird kein Eingabezeichen gelesen.
ε als Kellerersatz: Das oberste Kellerzeichen wird entfernt, ohne ein neues Kellerzeichen zu schreiben.

Schülernahe Sicht

Der Automat sieht immer nur die aktuelle Eingabe, den aktuellen Zustand und das oberste Kellerzeichen. Alles darunter bleibt gespeichert, kann aber erst sichtbar werden, wenn die Zeichen darüber abgebaut sind.

Übergänge eines Kellerautomaten
Wie Eingabe und Keller gemeinsam den nächsten Schritt bestimmen

Anatomie einer PDA-Regel mit Zustand, Eingabe, Stack-Top, Folgezustand und Ersatz — Was man sieht: die Regelnotation `(q, a, A) → (q', γ)`. Begriff: Abhängigkeit von Zustand, Eingabe und Kelleroberseite. Lernpunkt: Genau diese Lesefähigkeit ist für abiturtypische PDA-Aufgaben zentral.

Regel lesen und Trace deuten

Beim endlichen Automaten genügt eine Regel der Form δ(Zustand, Eingabesymbol). Beim Kellerautomaten braucht die Regel zusätzlich die Kelleroberseite. Sie beschreibt also: aktueller Zustand + Eingabesymbol oder ε + Kelleroberseite → Folgezustand + Kellerersatz.

ε als Eingabe bedeutet: Schritt ohne Eingabezeichen.
ε als Kellerersatz bedeutet: Pop, also Entfernen des obersten Kellerzeichens.
Der Trace im Werkzeug zeigt pro Schritt Zustand, Restwort, Keller und angewendete Regel.

Worterkennung
Akzeptanzbedingungen bei Kellerautomaten

Ein Kellerautomat verarbeitet ein Eingabewort Zeichen für Zeichen und verändert gleichzeitig seinen Keller. Ein einzelner Zustand reicht deshalb nicht mehr aus, um einen Verarbeitungsschritt zu beschreiben.

Konfiguration

Eine Konfiguration besteht aus aktuellem Zustand, Restwort und Kellerinhalt. Der Trace im Werkzeug zeigt also nicht nur Zustände wie bei Q3.2, sondern zusätzlich das noch nicht gelesene Restwort und die Entwicklung des Kellers.

Akzeptanz durch Endzustand

nach kompletter Eingabe wird ein Endzustand erreicht
der aktuelle Kellerinhalt kann je nach Aufgabenstellung zusätzlich relevant sein

Akzeptanz durch leeren Keller

nach kompletter Eingabe ist der Keller bis auf das Bodensymbol abgebaut oder ganz leer
dies wird in vielen Schulbeispielen explizit vorgegeben

Merke

Welche Akzeptanzbedingung gilt, ist Teil der Modellfestlegung oder der Aufgabenstellung: Endzustand, leerer Keller oder eine ausdrücklich geforderte Kombination.

Im Werkzeug kannst du zwischen final_state und empty_stack unterscheiden. Fachlich entscheidet immer die konkrete Aufgabenstellung, welche Akzeptanz gilt.

Beispiel: Sprache a^n b^n
Wie der Keller gleiche Anzahlen von a und b prüft

Betrachte die Sprache L = { a^n b^n | n >= 1 }. Q3.2 liefert hier den Grenzfall: Ein endlicher Automat kann für beliebiges n nicht speichern, wie viele a vorher gelesen wurden. Die Sprache ist nicht regulär, aber kontextfrei.

Für jedes gelesene a wird ein A auf den Keller gelegt.
Für jedes gelesene b wird ein A vom Keller entfernt.
Wenn nach allen b genau die passenden Marker abgebaut sind, stimmen die Anzahlen.
Der Keller übernimmt damit den unbeschränkten Anzahlvergleich, den ein DEA/NEA nicht leisten kann.

Konfigurations-Trace für das Eingabewort aabb im pda-anbn-Preset — Was man sieht: Konfigurationen aus Zustand, Restwort und Keller für `aabb`. Begriff: Konfigurationsfolge beim Kellerautomaten. Lernpunkt: Der Keller übernimmt den Anzahlvergleich zwischen `a` und `b`.

Mit dem Werkzeug prüfen

Im Automaten-/Formalsprachen-Werkzeug: Bereich Kellerautomat / Speicherautomat öffnen, Preset pda-anbn laden, Eingabewort testen und Trace plus Stack-Trace auswerten.

gültig: ab, aabb, aaabbb
ungültig: aab, abb, ba

Vertiefung (LK): Nichtdeterministischer Kellerautomat
Mehrere mögliche Rechenwege als zentrales Modellprinzip

Ein nichtdeterministischer Kellerautomat kann in derselben Situation mehrere mögliche Übergänge haben. Ein Eingabewort wird akzeptiert, wenn mindestens ein möglicher Rechenweg akzeptiert.

Nichtdeterminismus ist ein mathematisches Modell, kein magisches gleichzeitiges Rechnen.
Ein Eingabewort wird akzeptiert, wenn mindestens ein möglicher Rechenweg in eine akzeptierende Situation führt.
Das Werkzeug zeigt Mehrdeutigkeit an und folgt für die Einzelschritt-Simulation einer Regelpriorität.
Anschluss an Q3.2: Bei endlichen Automaten kann ein NEA wieder durch einen DEA simuliert werden.
Bei Kellerautomaten ist der nichtdeterministische Blick für die volle Klasse der kontextfreien Sprachen wesentlich.

Kontextfreie Sprachen und Rekursion
Brücke von Grammatiken zu Kellerautomaten

In Q3.1 hast du gesehen: Kontextfreie Grammatiken haben links genau ein Nicht-Terminal und können rekursive oder geschachtelte Strukturen erzeugen. Q3.3 liefert dazu die erkennende Automatenperspektive: Ein Kellerautomat kann solche Strukturen mit Hilfe seines Stacks prüfen.

Klammerausdrücke mit beliebiger Schachtelung
Sprachen wie a^n b^n
einfache rekursive Sprachmuster
anschaulich: verschachtelte HTML-ähnliche Strukturen

Leitgedanke

Der Keller passt gut zu Rekursion: Hineingehen bedeutet speichern, Zurückkehren bedeutet abbauen.

Grenzen des Kellerautomaten
Mächtiger als endliche Automaten, aber nicht allmächtig

Kellerautomaten sind mächtiger als endliche Automaten, aber sie bleiben begrenzt. Ein einzelner Stack kann gut eine verschachtelte Rückkehrstruktur oder einen Anzahlvergleich wie a^n b^n verwalten. Die Sprache { a^n b^n c^n | n >= 1 } ist dagegen nicht kontextfrei: Ein Kellerautomat mit einem einzelnen Stack kann drei gekoppelte Anzahlbereiche nicht allgemein erkennen.

Gut geeignet

a^n b^n
korrekt geschachtelte Klammern

Nicht allgemein mit einem Kellerautomaten erkennbar

{ a^n b^n c^n | n >= 1 } ist nicht kontextfrei
ein einzelner Stack reicht nicht für drei gekoppelte Anzahlbereiche
dafür braucht man mehrere Speicher oder ein mächtigeres Modell

Werkzeug: Automaten-/Formalsprachen-Werkzeug (Kellerautomat, Stack-Trace, Worterkennung)

Der Werkzeuganschluss bündelt die operative Seite dieses Kapitels: Du lädst einen Kellerautomaten, testest ein Eingabewort und liest den Trace als Folge von Konfigurationen. Entscheidend ist dabei nicht nur, welcher Zustand erreicht wird, sondern wie Restwort und Kellerinhalt sich Schritt für Schritt verändern.

Preset pda-parentheses laden und Klammerausdrücke prüfen
Preset pda-anbn laden und Wörter wie ab, aabb oder aab testen
Konfigurationen lesen: Zustand, Restwort, Kellerinhalt
Stackoperationen push, pop und replace im Trace nachvollziehen
ε-Schritte und ε als Kellerersatz unterscheiden
Akzeptanzbedingung prüfen: final_state oder empty_stack

Automaten-/Formalsprachen-Werkzeug öffnen

Merksätze

Ein Kellerautomat ist ein endlicher Automat mit zusätzlichem Keller/Stack.
Der Keller arbeitet nach dem LIFO-Prinzip.
Ein Übergang hängt von Zustand, Eingabesymbol oder ε und oberstem Kellerzeichen ab.
Eine Konfiguration eines Kellerautomaten besteht aus Zustand, Restwort und Kellerinhalt.
Klammerausdrücke und a^n b^n zeigen, warum Speicher nötig ist.
Nichtdeterministische Kellerautomaten erkennen die kontextfreien Sprachen; deterministische Varianten sind eingeschränkter.
Nichtdeterminismus ist beim Kellerautomaten für die volle Klasse der kontextfreien Sprachen zentral.
Kellerautomaten sind mächtiger als endliche Automaten, aber weiterhin begrenzt.
Abituraufgaben legen fest, ob durch Endzustand, leeren Keller oder eine Kombination akzeptiert wird.

Ausblick

Nach Q3.1 bis Q3.3 wird sichtbar, wie Speicherformen Sprachklassen prägen: Ohne zusätzlichen Speicher erkennt der endliche Automat reguläre Sprachen; mit einem Stack erkennt der Kellerautomat kontextfreie Strukturen. Q3.4 erweitert diesen Weg zum allgemeineren Bandmodell der Turingmaschine.