Kellerautomaten

Wir haben gesehen, dass die Sprache der korrekt geklammerten Ausdrücke nicht regulär ist. Das liegt vor Allem daran, dass sich der Automat nicht "merken" kann, wie viele öffnende Klammern er schon konsumiert hat. Um dies zu erreichen, muss man dem Automaten ein Hilfsmittel geben. Auf Englisch nennt man dieses Hilfsmittel Stack. Auf deutsch nennt man es in der Fachsprache oft Stapelspeicher, aber irgendjemand hat es wohl besonders schlau gefunden, "Stack" mit "Keller" zu übersetzen, weshalb man in der theoretischen Informatik jetzt also häufig von "Kellern" redet, obwohl "Stapelspeicher" der sinnvollere Begriff wäre.

Ein Keller (oder Stapelspeicher) ist eine Folge von Zeichen aus einem Alphabet $\cal L$, und funktioniert dabei so wie ein Stapel Teller: Nach dem Last-In-First-Out-Prinzip (LIFO-Prinzip): Zunächst existiert der leere Stapel $[]$. Auf einen gegebenen Stapel $s$ kann man mittels push ein Zeichen $z\in{\cal L}$ hinzufügen, der resultierende Stapel sieht dann so aus: $z :: s$. Wir schreiben $[z]$ für $z :: []$, und generell schreiben wir $[z, z_1, \ldots, z_k]$ für $z :: [z_1,\ldots,z_k]$. Ist der Stapel nicht leer, können wir mittels peek dessen höchstes Element auslesen, also im Falle von $z :: r$ eben $z$. Mittels pop können wir beim nichtleeren Stapel dieses Element entfernen, also aus $z :: r$ wieder $r$ machen.

Beispiel:

• Sei begonnen mit dem leeren Stapel []
• push 1 macht daraus [1]
• push 2 macht daraus [2 1]
• push 3 macht daraus [3 2 1]
• peek liefert nun 3 zurück
• pop macht daraus wieder [2 1]
• peek liefert nun 2 zurück
• push 4 macht daraus [4 2 1]
• peek liefert nun 4 zurück

Ein Kellerautomat ist nun ein Automat, der zusätzlich einen Keller besitzt. Bei jedem Übergang wird nun also nicht nur ein Zeichen konsumiert, sondern es wird auch überprüft welches Zeichen auf dem Stack ganz oben ist, bzw. ob der Stack leer ist, also ein peek, und eventuell wird dabei ein weiteres Zeichen auf den Stack gepusht, oder es wird gepopt. Die Sprache der korrekt geklammerten Ausdrücke kann nun mit dem folgenden Kellerautomaten akzeptiert werden:

                +----(,push 1-----+
                |                 |
         --->((0))<---------------+--+
                |                    |
                +----), peek=1, pop--+

Kellerautomaten sind also etwas mächtiger als endliche Automaten, weil sie sich in Grenzen Zwischenergebnisse merken können. Es zeigt sich aber, dass auch Kellerautomaten nicht alle Sprachen akzeptieren können.