Kellerautomat
# Kellerautomat

Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der theoretischen Informatik, ein Konstrukt, das verwendet wird, um gewisse Eigenschaften von Problemen und Algorithmen zu analysieren und zu beweisen.
Der Kellerautomat ist ein endlicher Automat, der um einen Kellerspeicher (a.g. Stack) erweitert wurde. Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur Turingmaschine.

## Funktionsweise

Ein Kellerautomat dient dazu, zu klären, ob eine Eingabe (d. h. ein Wort aus null, einem oder mehreren Zeichen) zu einer bestimmten formalen Sprache (d. h. einer Menge von Wörtern) gehört. Dafür arbeitet der Automat das Eingabewort Schritt für Schritt von links nach rechts ab und kann dabei eine Reihe von Zuständen annehmen. Zu Anfang ist er im sogenannten Startzustand. Typischerweise wird in jedem Verarbeitungsschritt ein Zeichen aus der Eingabe gelesen. Außerdem wird in jedem Verarbeitungsschritt das oberste Zeichen vom Keller gelesen, d. h. entfernt. Abhängig vom aktuellen Zustand, dem gerade gelesenen Eingabezeichen und dem gerade gelesenen Kellerzeichen geht der Automat in einen neuen Zustand über und legt anstelle des entfernten Kellerzeichens ein neues Wort auf dem Keller ab. Wenn die gesamte Eingabe gelesen wurde und der Keller leer ist, gehört die Eingabe zur vom Automaten erkannten Sprache.
Allgemein sind allerdings mehrere Abweichungen von der obigen Erklärung möglich:
* Die erkannte Sprache kann auch als die Menge der Wörter definiert werden, bei deren Abarbeitung der Kellerautomat einen sogenannten Endzustand erreicht – unabhängig davon, ob dabei der Keller geleert wird.
* Nicht in jedem Verarbeitungsschritt muss ein Zeichen aus der Eingabe gelesen werden. Wenn keins gelesen wurde, wird das gelesene Wort als $\varepsilon$ (das leere Wort) bezeichnet.
* Für manche Kombinationen von Zustand, Eingabezeichen (oder $\varepsilon$) und Kellerzeichen kann der Kellerautomat die Wahl zwischen mehreren Übergängen (also Kombinationen von Folgezustand und Kellerwort) haben. Die Eingabe gilt in diesem Fall als erkannt, wenn der Keller geleert werden kann bzw. ein Endzustand erreicht werden kann.

### Beispiel

Um das Prinzip eines Kellerautomaten zu verdeutlichen, wird häufig die syntaktische Untersuchung geklammerter Ausdrücke herangezogen. Beispielsweise muss in einem Ausdruck einer bestimmten Sprache zu jeder öffnenden Klammer auch eine schließende Klammer existieren:
    Beispiel: { … { … } … }
Der Automat beginnt in einem Startzustand z0; im Keller befindet sich ein Zeichen, welches das Ende kennzeichnet (#). Bei der Abarbeitung des Ausdrucks bewegt sich der Lesekopf Zeichen für Zeichen weiter. Stößt er dabei auf eine öffnende Klammer, so wird diese in den Keller geschrieben. Tritt in der weiteren Abarbeitung eine schließende Klammer auf, so wird das oberste Klammer-auf-Zeichen im Keller wieder gelöscht. Der Ausdruck ist dann erfolgreich abgearbeitet, wenn der Lesekopf das Ende des Eingabebandes erreicht hat und sich im Keller ausschließlich das Zeichen # befindet. Befände sich hingegen noch eine geöffnete Klammer nach der Ausdrucksabarbeitung im Keller, so würde dies bedeuten, dass eine schließende Klammer fehlt und ein syntaktischer Fehler vorliegt. Auch wenn das Ende des Kellers erreicht wird, bevor die Eingabe vollständig abgearbeitet wurde, liegt ein Fehler vor. In diesem Fall befinden sich zu viele schließende Klammern in der Eingabe.

## Formale Definition

Ein nichtdeterministischer Kellerautomat (NKA) wird definiert als ein 7-Tupel $M=(Z,\Sigma ,\Gamma ,\delta ,z_{0},\#,F)$, wobei
* $Z\,$ eine endliche Menge von Zuständen,
* $\Sigma \,$ ein Eingabealphabet,
* $\Gamma \,$ das Kelleralphabet,
* $\delta \,$ die Zustandsübergangsfunktion, $\delta \colon Z\times (\Sigma \cup \{\varepsilon \})\times \Gamma \rightarrow {\mathcal {P}}(Z\times \Gamma ^{*})$, die nur auf endliche Teilmengen von $Z\times \Gamma ^{*}$ abbildet,
* $z_{0}\in Z$ der Startzustand,
* $\#\in \Gamma$ das Anfangssymbol im Keller und
* $F\subseteq Z$ eine Menge von Endzuständen
ist.
Dabei bezeichnet $\varepsilon$ das leere Wort und $\Gamma ^{*}$ die Menge der Wörter des Alphabets $\Gamma$.
Manchmal findet man auch Kellerautomaten als 6-Tupel $M=(Z,\Sigma ,\Gamma ,\delta ,z_{0},\#)$, in diesem Fall gibt es keine Endzustände, und der Kellerautomat akzeptiert ein Wort, falls nach der Abarbeitung des Wortes der Keller leer ist.
Wenn die Übergangsfunktion die Eigenschaft $\forall z\in Z,\forall a\in \Sigma ,\forall g\in \Gamma ,\left|\delta (z,a,g)\right|+\left|\delta (z,\varepsilon ,g)\right|\leq 1$ erfüllt, spricht man von einem deterministischen Kellerautomaten. Zu einer festen Eingabe gibt es dann höchstens eine Zustandsübergangsabfolge, Mehrdeutigkeiten können also nicht auftreten.