Mit Google fortfahren
Kellerautomat einfach erklärt: Aufbau und Beispiel
Ein Kellerautomat ist ein endlicher Automat mit einem zusätzlichen Stapelspeicher. Dadurch kann er sich eine beliebig lange Folge von Symbolen merken und später in umgekehrter Reihenfolge wieder abgleichen. So erkennt er zum Beispiel gleich viele aufeinanderfolgende a und b oder korrekt verschachtelte Klammern.
Auf dieser Seite lernst du, wie der Keller arbeitet, wie Übergänge gelesen werden und wie du einen Lauf für die Sprache aⁿbⁿ nachvollziehst.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Warum braucht ein Automat einen Keller?
Ein endlicher Automat besitzt nur endlich viele Zustände. Er kann deshalb nicht für beliebig große Zahlen festhalten, wie viele a er bereits gelesen hat. Ein Kellerautomat ergänzt ihn um einen Speicher, dessen Länge nicht von vornherein begrenzt ist.
Kellerspeicher
Ein Keller oder Stack speichert Symbole nach dem LIFO-Prinzip: Last In, First Out. Das zuletzt abgelegte Symbol wird zuerst wieder entfernt. Die zugängliche Stelle heißt Kelleroberseite.
Stell dir einen Stapel Teller vor: Du legst einen Teller oben ab (push) und nimmst ebenfalls den obersten Teller herunter (pop). An tiefer liegende Teller kommst du erst, wenn du alle darüber entfernt hast.
Bei einer Klammerprüfung kann der Automat für jede öffnende Klammer ( ein Symbol ablegen. Für jede schließende Klammer ) entfernt er eines. Soll er entfernen, obwohl kein passendes Symbol mehr da ist, liegt eine schließende Klammer zu viel vor. Bleiben am Ende Symbole übrig, fehlen schließende Klammern.
Der Keller speichert beliebig viele Symbole, aber der Automat sieht und verändert immer nur die Kelleroberseite.
Wie beschreibt eine Übergangsregel einen Schritt?
Ein Kellerautomat betrachtet bei einem Schritt drei Dinge:
- seinen aktuellen Zustand,
- das nächste Eingabezeichen oder
ε, - das Symbol an der Kelleroberseite.
Die passende Regel legt den Folgezustand und ein Ersatzwort für das entfernte oberste Kellersymbol fest. Das Kelleralphabet darf neben Eingabezeichen auch Hilfssymbole enthalten. Häufig markiert # den Kellerboden.
Epsilon
ε bezeichnet das leere Wort. Steht ε an der Eingabestelle, verbraucht der Übergang kein Eingabezeichen. Steht ε als Kellerersatz, wird das oberste Symbol gelöscht und nichts zurückgelegt.
Wir schreiben eine Regel hier in der Form:
Zustand, Eingabe, oben → Folgezustand, Ersatz
Die Regel q0, a, # → q0, A# bedeutet:
- Der Automat befindet sich in
q0, liest einaund sieht oben#. - Er verbraucht das
a. - Er entfernt
#und ersetzt es durchA#. - Er bleibt in
q0.
Dabei steht die Kelleroberseite links. Nach dem Schritt liegt also A über dem Bodensymbol #.
Drei typische Kelleraktionen sind:
| Ersatz | Wirkung |
|---|---|
| dasselbe Symbol | Keller bleibt unverändert |
| zusätzliches Symbol vor dem alten | Symbol wird oben abgelegt |
ε | oberstes Symbol wird entfernt |
Wie erkennt der Automat Wörter der Form aⁿbⁿ?
Wir betrachten die Sprache aller Wörter mit mindestens einem a, gefolgt von genau gleich vielen b. Beispiele sind ab, aabb und aaabbb. Dagegen gehören aabbb und abab nicht dazu.
Der entscheidende Zusammenhang lautet: Für jedes gelesene a wird ein A gespeichert; für jedes spätere b wird genau ein A entfernt.
Der Automat verwendet drei Zustände:
q0:alesen und speichern,q1:blesen und mit gespeichertenAabgleichen,q2: akzeptierender Endzustand.
| Zustand | Eingabe | oben | Folgezustand | Ersatz |
|---|---|---|---|---|
q0 | a | # | q0 | A# |
q0 | a | A | q0 | AA |
q0 | b | A | q1 | ε |
q1 | b | A | q1 | ε |
q1 | ε | # | q2 | ε |
Nicht aufgeführte Situationen besitzen keinen Übergang. Der Lauf scheitert dann.
So verarbeitet der Automat aabb. Wir notieren jeweils (Zustand, Resteingabe, Keller):
- Start:
(q0, aabb, #) - erstes
aspeichern:(q0, abb, A#) - zweites
aspeichern:(q0, bb, AA#) - erstes
babgleichen:(q1, b, A#) - zweites
babgleichen:(q1, ε, #) - Bodensymbol ohne Eingabeverbrauch entfernen:
(q2, ε, ε)
Die Eingabe ist vollständig gelesen, der Keller ist leer und q2 ist erreicht. Das Wort wird akzeptiert.
Warum scheitert aabbb? Nach zwei b liegt nur noch # oben. Für ein weiteres b gibt es keine Regel. Warum scheitert aaabb? Nach der Eingabe liegt noch ein A im Keller; der Übergang nach q2 ist nicht möglich.
Zuerst speichert der Automat die Anzahl der a. Danach verwendet er jedes b, um genau ein gespeichertes A zu löschen. Akzeptiert wird nur, wenn Eingabe und Speicher passend enden.
Wann wird ein Lauf akzeptiert?
Eine Konfiguration ist eine Momentaufnahme des Automaten. Sie enthält den aktuellen Zustand, die noch nicht gelesene Eingabe und den gesamten Kellerinhalt. So lässt sich ein Lauf Schritt für Schritt prüfen.
Für Kellerautomaten werden verschiedene Akzeptanzbedingungen verwendet:
- durch leeren Keller: Die Eingabe ist vollständig gelesen und der Keller ist leer;
- durch Endzustand: Die Eingabe ist vollständig gelesen und ein festgelegter Endzustand ist erreicht;
- bis zum Bodensymbol geleert: Die Eingabe ist vollständig gelesen und nur
#bleibt zurück.
Diese Bedingungen darfst du nicht still vermischen. Lies bei jeder Aufgabe zuerst, welche Konvention gilt. Der Beispielautomat im vorigen Kapitel erfüllt am Ende gleichzeitig leeren Keller und Endzustand.
Bei nichtdeterministischen Kellerautomaten lassen sich Akzeptanz durch Endzustand und durch leeren Keller so ineinander übersetzen, dass dieselbe Sprachklasse erkannt wird. Bei deterministischen Kellerautomaten sind diese Varianten im Allgemeinen nicht gleichmächtig.
Was bedeuten deterministisch und nichtdeterministisch?
Ein deterministischer Kellerautomat hat in jeder Konfiguration höchstens einen möglichen nächsten Schritt. Wenn für einen Zustand und eine Kelleroberseite ein ε-Übergang möglich ist, darf nicht zugleich ein Übergang mit dem nächsten Eingabezeichen zur Wahl stehen.
Der Automat für aⁿbⁿ ist deterministisch: Am ersten b ist eindeutig erkennbar, dass die Speicherphase endet und die Vergleichsphase beginnt.
Ein nichtdeterministischer Kellerautomat darf mehrere mögliche Schritte anbieten. Ein Wort gilt als akzeptiert, wenn mindestens ein möglicher Berechnungspfad die festgelegte Akzeptanzbedingung erfüllt. Andere Pfade dürfen scheitern.
Bei einem Palindrom wie abba muss der Automat zunächst a und b speichern und danach die zweite Hälfte dagegen prüfen. Ohne besonderes Trennzeichen ist beim Lesen nicht sichtbar, wo die Mitte liegt. Ein nichtdeterministischer Automat kann den Umschaltpunkt erraten. Für ungerade Längen muss er zusätzlich die Möglichkeit berücksichtigen, das mittlere Zeichen nicht abzugleichen.
Welche Sprachen können Kellerautomaten erkennen?
Nichtdeterministische Kellerautomaten erkennen genau die kontextfreien Sprachen. Zu jeder kontextfreien Grammatik gibt es einen gleichmächtigen nichtdeterministischen Kellerautomaten und umgekehrt.
Endliche Automaten erkennen die regulären Sprachen. Sie können nur endlich viele Zustände als Gedächtnis verwenden. Deshalb können sie die unbeschränkte Abhängigkeit in aⁿbⁿ nicht speichern: Für beliebig große n müssten sie sich beliebig viele gelesene a merken.
Deterministische Kellerautomaten erkennen nur einen echten Teil der kontextfreien Sprachen. Die Beziehung lässt sich so ordnen:
- reguläre Sprachen: durch endliche Automaten erkennbar;
- deterministisch-kontextfreie Sprachen: durch deterministische Kellerautomaten erkennbar;
- kontextfreie Sprachen: durch nichtdeterministische Kellerautomaten erkennbar.
Jede reguläre Sprache ist auch deterministisch-kontextfrei, und jede deterministisch-kontextfreie Sprache ist kontextfrei. Die Umkehrungen gelten nicht allgemein.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Ein Keller arbeitet nach dem -Prinzip. Ein nichtdeterministischer Kellerautomat erkennt genau die -Sprachen. Bei aⁿbⁿ wird für jedes a ein Symbol und für jedes b eines gelöscht.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Kellerautomat
- Aufbau
- endliche Zustände
- Eingabealphabet
- LIFO-Keller mit Bodensymbol
- Übergangsregeln
- Arbeitsweise
- Symbol ablegen
- oberstes Symbol ersetzen oder löschen
- Eingabezeichen lesen oder ε-Schritt ausführen
- Akzeptanz
- Eingabe vollständig lesen
- festgelegte Konvention beachten
- Varianten
- deterministisch: höchstens ein Folgeschritt
- nichtdeterministisch: ein erfolgreicher Pfad genügt
- Sprachmächtigkeit
- `aⁿbⁿ` mit Speicher- und Vergleichsphase
- nichtdeterministisch genau kontextfreie Sprachen
- Aufbau
Abschluss-Check
Kannst du nun einen Lauf notieren, eine Regel ausführen und bei einer Aufgabe zuerst die Akzeptanzkonvention bestimmen? Dann hast du die drei wichtigsten Werkzeuge für Kellerautomaten sicher verbunden.