Kellerautomat
Ein Kellerautomat ist ein endlicher Automat mit zusätzlichem Speicher. Damit kann er verschachtelte Strukturen wie Klammern prüfen.
Definition
Ein Kellerautomat ist ein 7-Tupel [math]\displaystyle{ M = (Q, \Sigma, \Gamma, \delta, q0, \#, F) }[/math]. Wie beim endlichen Automaten ist [math]\displaystyle{ Q }[/math] die endliche, nicht leere Zustandsmenge, [math]\displaystyle{ \Sigma }[/math] das Eingabealphabet, [math]\displaystyle{ \delta }[/math] die Übergangsfunktion (siehe Formale Darstellung), [math]\displaystyle{ q0 \in Q }[/math] der Startzustand und [math]\displaystyle{ F \subseteq Q }[/math] die Menge der Endzustände. Zusätzlich besitzt der Kellerautomat:
- das Kelleralphabet [math]\displaystyle{ \Gamma }[/math], die Menge der Zeichen, die im Keller liegen dürfen,
- das Kellerbodensymbol [math]\displaystyle{ \# \in \Gamma }[/math], das den Boden des Kellers markiert und zu Beginn als einziges Zeichen im Keller liegt.
Der Keller arbeitet nach dem LIFO-Prinzip (last in, first out) wie ein Stapel. Der Automat sieht nur das oberste Zeichen. Das zuletzt abgelegte Zeichen wird als Erstes wieder entfernt.
Arbeitsweise
Jeder Schritt berücksichtigt den Zustand, das nächste Eingabezeichen oder [math]\displaystyle{ \varepsilon }[/math] (dann liest der Automat kein Zeichen) und das oberste Kellerzeichen. Diese drei Angaben bilden die Lage des Automaten. Der Automat wechselt den Zustand und ersetzt das oberste Kellerzeichen durch ein Wort aus Kellerzeichen. Je nach Ersatzwort wirkt der Schritt so auf den Keller:
- Ablegen: Das Ersatzwort ist länger als ein Zeichen. Der Keller wird höher.
- Entfernen: Das Ersatzwort ist leer. Das oberste Zeichen verschwindet.
- Unverändert lassen: Das Ersatzwort besteht nur aus dem bisherigen obersten Zeichen.
Akzeptanz
Der Kellerautomat akzeptiert ein Wort, wenn die Eingabe vollständig gelesen ist und ein Endzustand erreicht wurde. Gibt es in einer Lage keinen passenden Übergang, bricht der Automat ab und lehnt das Wort ab.
Andere Quellen akzeptieren stattdessen bei leerem Keller. Deterministische Kellerautomaten erkennen nicht alle kontextfreien Sprachen.
Formale Darstellung
Die Übergangsfunktion hat die Form [math]\displaystyle{ \delta: Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to Q \times \Gamma^* }[/math]. Sie ordnet dem Zustand, dem Eingabezeichen (oder [math]\displaystyle{ \varepsilon }[/math]) und dem obersten Kellerzeichen einen Folgezustand und ein Ersatzwort zu.
In der Tabelle steht jede Zeile für einen Übergang mit den Spalten Zustand, Eingabe, oberstes Kellerzeichen, Folgezustand und Ersatzwort. Ein Ersatzwort wird von links nach rechts geschrieben, sein letztes Zeichen liegt danach oben. Beim deterministischen Automaten passt in jeder Lage höchstens eine Zeile.
Beispiele
Klammerausdruck mit einem Keller prüfen
Der Kellerautomat prüft, ob jede öffnende Klammer eine passende schließende hat. Er hat die Zustände q0 (Startzustand und Endzustand) und q1, das Eingabealphabet [math]\displaystyle{ \Sigma = \{(, )\} }[/math] und das Kelleralphabet [math]\displaystyle{ \Gamma = \{\#, K\} }[/math]. Jedes ( legt ein K ab, jedes ) entfernt ein K.
| Zustand | Eingabe | oben im Keller | Folgezustand | ersetzt durch |
|---|---|---|---|---|
| q0 | ( |
# |
q1 | #K
|
| q1 | ( |
K |
q1 | KK
|
| q1 | ) |
K |
q1 | ε |
| q1 | ε | # |
q0 | #
|
Der Keller wird von links nach rechts geschrieben, oben steht rechts. Das Protokoll zeigt den Lauf für (()). Zu Beginn liegt nur # im Keller.
| Schritt | Zustand | Resteingabe | Keller (oben rechts) |
|---|---|---|---|
| 0 | q0 | (()) |
#
|
| 1 | q1 | ()) |
#K
|
| 2 | q1 | )) |
#KK
|
| 3 | q1 | ) |
#K
|
| 4 | q1 | ε | #
|
| 5 | q0 | ε | #
|

In Schritt 4 liegt nur noch # im Keller. Schritt 5 ist der ε-Übergang: Er führt ohne Eingabezeichen nach q0. Am Ende ist alles gelesen, und q0 ist ein Endzustand. Der Automat akzeptiert (()).
Abgelehntes Wort protokollieren
Das Protokoll für (() zeigt, warum der Automat dieses Wort ablehnt.
| Schritt | Zustand | Resteingabe | Keller (oben rechts) |
|---|---|---|---|
| 0 | q0 | (() |
#
|
| 1 | q1 | () |
#K
|
| 2 | q1 | ) |
#KK
|
| 3 | q1 | ε | #K
|
Alles ist gelesen, aber ein K liegt noch im Keller. Der Automat steht in q1, und q1 ist kein Endzustand. Für q1 mit K oben gibt es keinen Übergang ohne Eingabezeichen, der Automat bricht ab. Er lehnt (() ab.