Kellerautomaten

In dieser Lehreinheit lernst du Kellerautomaten kennen. Einfach gesagt, sind das endliche Automaten mit einem zusätzlichen sogenannten Kellerspeicher (Stack). Wenn du dir bei den endlichen Automaten noch unsicher bist, kannst du dir hier noch einmal die entsprechende Lehreinheit anschauen. Vor allem solltest du bereits wissen, was ein Automat überhaupt ist und wie nichtdeterministische Automaten funktionieren.

Wie auch schon die Turingmaschinen und die endlichen Automaten helfen uns die Kellerautomaten zu verstehen, wo die Möglichkeiten und Grenzen verschieden mächtiger Rechenmodelle liegen. In der Praxis ist eine wichtige Aufgabe von Kellerautomaten die Syntaxanalyse beim Kompilieren von Programmiersprachen, außerdem waren früher die Gleitkommaeinheiten von Intel-Prozessoren so aufgebaut.

Nichtdeterministische Kellerautomaten

Wir beschäftigen uns in dieser Lehreinheit speziell mit nichtdeterministischen Kellerautomaten. Diese werden mit nPDA (oder einfach nur PDA) abgekürzt, was vom englischen nondeterministic pushdown automaton stammt. Genau wie die endlichen Automaten können PDAs eine Eingabe Zeichen für Zeichen von links nach rechts lesen und sie dann entweder akzeptieren oder verwerfen. Da sie nichtdeterministisch sind, können sie dabei von einem Zustand in gleich mehrere Nachfolgezustände übergehen. Neu ist jetzt der Kellerspeicher (eine LIFO-Datenstruktur), von dem der Automat bei jedem Zustandsübergang das oberste Zeichen liest; dieses wird genauso verbraucht wie bei der Eingabe. Der Nachfolgezustand ist nun nicht mehr nur vom Eingabezeichen abhängig, sondern auch von dem gelesenen Kellerzeichen. Nach dem Übergang schreibt der PDA eine neue Zeichenkette oben auf den Stack. Manchmal will der Automat auch nur aus dem Speicher lesen, aber dafür kein Zeichen der Eingabe verbrauchen. Genau das passiert bei einem sogenannten \(\varepsilon\)-Übergang.

Formale Definition

Ein nichtdeterministischer Kellerautomat \(M\) ist ein 6-Tupel \(M = (Q,\Sigma,\Gamma,\Delta,q_0,\#)\), sodass gilt:

• \(Q\) ist die endliche Menge von Zuständen,
• \(\Sigma\) ist das endliche Eingabealphabet,
• \(\Gamma\) ist das endliche Kelleralphabet,
• \(\Delta \colon Q \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to \mathcal{P}_{\text{fin}}(Q \times \Gamma^*)\) ist die Überführungsfunktion,
• \(q_0 \in Q\) ist der Startzustand,
• \(\# \in \Gamma\) ist das Anfangssymbol im Keller.

Dabei bezeichnet \(\mathcal{P}_{\text{fin}}(X)\) die Gesamtheit aller endlichen Teilmengen von \(X.\)

Gelegentlich findet man auch andere formale Definitionen von PDAs. Beispielsweise gibt man manchmal eine ganze Menge von Startzuständen an, es gibt zusätzlich eine Menge von Endzuständen, der Automat darf nur ein einziges Zeichen auf den Keller schreiben oder aber gleich mehrere Zeichen der Eingabe auf einmal lesen. Für nichtdeterministische Kellerautomaten sind aber all diese Definitionen gleichwertig.

Arbeitsweise

Ganz zu Beginn steht ein endliches Eingabewort (ein Element von \(\Sigma^*\)) auf dem Band, der Automat ist im Zustand \(q_0\) und im Keller steht nur das Zeichen \(\#\). Die weitere Arbeitsweise des Kellerautomaten wird von der Überführungsfunktion \(\Delta\) beschrieben: Sie bildet Tripel \((q,i,c),\) bestehend aus aus dem aktuellen Zustand \(q \in Q\), einem Eingabezeichen \(i \in \Sigma \cup \{\varepsilon\}\) (das auch das leere Wort \(\varepsilon\) sein kann) und einem Kellerzeichen \(c \in \Gamma,\) auf eine endliche Auswahl von Tupeln \((q',\alpha\)) aus Nachfolgezuständen \(q' \in Q\) und Kellerwörtern \(\alpha \in \Gamma^*\) ab.

Nehmen wir einmal an, dass der Automat oben im Bild gerade im Zustand \(q_1\) ist und es gilt \(\Delta(q_1,n,K) = \{ (q_1,K),(q_2,PROP),(q_3,\varepsilon)\}.\) Dann kann der Automat entweder im aktuellen Zustand bleiben und das gelesene \(K\) einfach wieder zurück auf den Stack schreiben oder er geht in den Zustand \(q_2\) über und verwandelt das Kellerwort dabei zu \(PROPELLER\) oder aber er geht in den Zustand \(q_3\) und schreibt überhaupt nichts zurück in den Keller. In allen drei Fällen rückt der Lesekopf auf dem Eingabeband einen Schritt weiter. Wie oben erwähnt, ist manchmal auch ein \(\varepsilon\)-Übergang möglich, bei dem kein Eingabezeichen gelesen wird. Das schreiben wir zum Beispiel als \(\Delta(q_1,\varepsilon,K) = \{(q_2,PROP)\}.\)

Automatengraphen

Alternativ zur formalen Definition können wir PDAs auch wieder als Automatengraphen darstellen. Die Darstellung als Graph ist in vielen Fällen kompakter und übersichtlicher.

Um mehrere gleichartige Regeln zusammenfassen zu können, benutzen wir die Variablen \(x\) und \(y,\) die hier für die Zeichen \(0\) oder \(1\) (nicht aber für \(\#\)) stehen. Für Situationen \((q,i,c),\) die in der Tabelle oder im Graphen nicht vorkommen, gilt dabei immer \(\Delta(q,i,c) = \emptyset.\) Das heißt, der Automat würde in diesem Fall die Bearbeitung abbrechen. Beachte, dass dieser PDA tatsächlich nichtdeterministisch ist: So kann er sich im Zustand \(q_0\) jederzeit entscheiden, kein weiteres Eingabezeichen zu lesen und stattdessen einen \(\varepsilon\)-Übergang nach \(q_1\) zu machen. Die dafür vorgesehenen Regeln (3) und (4) haben beide die gleichen Voraussetzungen, aber der Automat kann beim Übergang ein Zeichen aus dem Keller löschen oder auch nicht.

Kontextfreie Sprachen

Wir wollen Kellerautomaten dazu benutzen, das Eingabewort entweder zu akzeptieren oder zu verwerfen. Hierfür müssen wir noch das Akzeptanzverhalten von Kellerautomaten definieren. Das ist ein bisschen anders als bei den endlichen Automaten. Einfach gesagt, akzeptiert ein Kellerautomat ein Wort, wenn zu dem Zeitpunkt, an dem die gesamte Eingabe gelesen wurde, auch der Kellerspeicher komplett leer ist (noch nicht einmal das Startsymbol \(\#\) steht noch drin). Um das genau aufzuschreiben, brauchen wir den Begriff der Konfiguration und müssen definieren, wann eine Konfiguration ein Nachfolger einer andern ist.

Eine Konfiguration eines Kellerautomaten \(M\) ist ein Tripel \((q,\sigma,\gamma),\) sodass gilt:

• \(q \in Q\) ist der aktuelle Zustand,
• \(\sigma \in \Sigma^*\) ist die verbleibende Eingabe,
• \(\gamma \in \Gamma^*\) ist das aktuelle Kellerwort.

Eine Konfiguration \((q',\sigma',\gamma')\) heißt nun Nachfolger von \((q,\sigma,\gamma),\) falls es eine Situation \((q,i,c) \in Q \times (\Sigma \cup \{\varepsilon\})\times \Gamma\) und Kellerworte \(\alpha, \beta \in \Gamma^*\) gibt, sodass gilt:

• die verbleibende Eingabe \(\sigma\) lässt sich schreiben als \(i \sigma'\!, \)
• das aktuelle Kellerwort \(\gamma\) lässt sich schreiben als \(c \beta, \)
• \((q',\alpha) \in \Delta(q,i,c)\) ist eine Regel,
• das neue Kellerwort \(\gamma'\) lässt sich schreiben als \(\alpha\beta.\)

Das heißt, die Konfiguration \((q',\sigma',\gamma')\) geht durch genau einen Arbeitsschritt des PDAs aus der Konfiguration \((q,\sigma,\gamma)\) hervor. Wir schreiben dann \((q,\sigma,\gamma) \vdash (q',\sigma',\gamma').\) Lässt sich die Nachfolgekonfiguration durch endlich viele Schritte erreichen, so schreiben wir \((q,\sigma,\gamma) \vdash^* (q',\sigma',\gamma').\) Die von einem Kellerautomaten \(M\) akzeptierte Sprache ist nun \[L(M) = \{ \sigma \in \Sigma^* \mid \exists q \in Q \colon (q_0,\sigma, \#) \vdash^* (q,\varepsilon,\varepsilon) \},\] sie enthält also alle Eingabeworte, für die es eine endliche Folge von Arbeitsschritten gibt, die den Automaten vom Start zu einem Punkt führen, in dem sowohl das Eingabeband als auch der Keller leer sind. In welchem Zustand der Automat endet, ist hierbei egal. Formale Sprachen, für die es einen nichtdeterministischen Kellerautomaten gibt, der sie akzeptiert, heißen kontextfreie Sprachen.

Hier ist es wirklich wichtig, dass es ein nichtdeterministischer Kellerautomat ist. Es gibt nämlich kontextfreie Sprachen, die von keinem deterministischen Kellerautomaten erkannt werden können. Ein Beispiel findest du im nächsten Abschnitt.

Beispiele

Schauen wir uns das Akzeptanzverhalten des oben definierten PDAs \(M\) an; als Eingabewort nehmen wir \(0110110.\) Wir beschreiben die Arbeit des Automaten durch eine Folge von Konfigurationen. Zur besseren Übersicht schreiben wir außerdem an jeden Übergang die Nummer der Regel, die wir benutzt haben.

\((q_0,0110110,\#) \overset{(1)}{\vdash} (q_0,110110,0\#) \overset{(2)}{\vdash} (q_0,10110,10\#) \overset{(2)}{\vdash} (q_0,0110,110\#) \overset{(2)}{\vdash} \) \((q_0,110,0110\#) \overset{(4)}{\vdash} (q_1, 110, 110\#) \overset{(6)}{\vdash} (q_1, 10, 10\#) \overset{(6)}{\vdash} (q_1, 0, 0\#) \overset{(6)}{\vdash}\) \((q_1,\varepsilon,\#) \overset{(7)}{\vdash} (q_1,\varepsilon,\varepsilon)\)

Solange er im Zustand \(q_0\) ist, schreibt \(M\) die Eingabe in umgekehrter Reihenfolge Zeichen für Zeichen auf den Stack. Irgendwann geht er nichtdeterministisch in den Zustand \(q_1\) über. Dabei kann er entweder ein Zeichen vom Keller löschen — wie in diesem Beispiel — oder das Kellerwort unverändert lassen. Im Zustand \(q_1\) liest der Automat den Rest der Eingabe und vergleicht sie schrittweise mit dem Kellerwort. Ist der Vergleich erfolgreich, so wird zum Schluss noch das Kellerschlusszeichen \(\#\) durch einen \(\varepsilon\)-Übergang gelöscht und die Eingabe so akzeptiert. Wir sehen, dass die kontextfreie Sprache, die \(M\) akzeptiert, genau die Palindrome mit Buchstaben \(0\) und \(1\) sind. Findest du auch für die Eingabe \(0101001010\) eine akzeptierende Folge von Konfigurationen?

Es lässt sich übrigens zeigen, dass die Sprache der Palindrome vom keinem deterministischen PDA akzeptiert wird. Ein einfaches Beispiel für eine deterministisch kontextfreie Sprache ist \(L = \{a^n b^n \mid n > 0\}.\) Wenn man für diese Sprache einen Automaten bauen will, ist der einfachste Weg, für jeden der beiden Buchstaben einen eigenen Zustand zu benutzen. Der Startzustand liest alle \(a\)s ein und merkt sie sich im Kellerspeicher. Sobald das erste \(b\) gelesen wird, wechselt der Automat in den zweiten Zustand und verarbeitet den Rest der Eingabe. Ist die Anzahl der \(a\)s und \(b\)s gleich, wird am Ende noch das \(\#\)-Symbol gelöscht und das Wort akzeptiert.

Für jede mögliche Situation gibt es hier nur höchstens eine anwendbare Regel, deswegen ist der PDA \(M_{ab}\) deterministisch.

Was haben wir gelernt?

1. Kellerautomaten sind endliche Automaten mit einem Kellerspeicher.
2. Kellerautomaten akzeptieren, wenn sowohl die Eingabe als auch der Keller leer sind.
3. Die nichtdeterministischen PDAs akzeptieren die kontextfreien Sprachen.
4. Es gibt kontextfreie Sprachen, die von keinem deterministischen PDA akzeptiert werden.