Kellerautomaten

Ein Kellerautomat ist ein um einen Keller (Speicher nach dem Lifo-Prinzip) erweiterter endlicher Automat (Akzeptor). Er kann mit dessen Hilfe beliebig viele Zeichen speichern und in Abhängigkeit vom zuletzt gemerkten, d. h. oben auf dem Keller liegenden Zeichen Zustandsübergänge vollziehen. Dabei wird entweder ein neues Zeichen in den Keller gelegt (Operation push), oder das oberste Zeichen wird aus dem Keller gelesen (und entfernt) (Operation pop).

Der Kellerautomat soll eine Entscheidung treffen und uns diese am Ende durch besondere Zustände anzeigen; deshalb benötigen wir hier kein Ausgabeband. Der Kellerautomat besitzt zwei spezielle Zustände. Wenn er seine Arbeit beendet, soll er in genau einen von beiden gehen und aufhören zu arbeiten. Einen dieser Zustände wird interpretiert als "Der Automat akzeptiert die Eingabe", der anderen als "Der Automat akzeptiert die Eingabe nicht". Der Lesekopf kann halten (H) oder nach rechts gehen (R).

Da durch die Verwendung eines Kellerspeichers jeweils das letzte eingeschriebene Zeichen gelesen werden kann, ist ein solcher Kellerautomat besonders für die LR(1)-Analyse einer Sprache geeignet.

Definition des Kellerautomaten

Definition: Kellerautomat

Ein Kellerautomat ist ein 7 Tupel $KA~=(X,K,Z,\delta,k_o,z_o,Z_E)$, wobei gilt: X ist eine nicht leere, endliche Menge, das Eingabealphabet, K ist eine nicht leere, endliche Menge, das Speicher oder Kelleralphabet, Z ist eine nicht leere, endliche Menge, die Zustandsmenge, $\delta$ ist die Überführungsfunktion $(X \times K \times Z) \rightarrow (Z \times K^*)$, $k_o \in K$ ist das Kellerleerzeichen, $z_o \in Z$ ist der Anfangszustand, $Z_E \in Z$ ist die Menge der Endzustände.

Die Überführungsfunktion $\delta$ sieht kompliziert aus, weil sie die komplexe Arbeitsweise des Automaten wiedergeben muss.

Arbeitsweise des Kellerautomaten

Der Automat liest im Zustand z ein Zeichen x auf dem Eingabeband (oder das Eingabeende eof) sowie das oberste Kellerzeichen k. Gemäß seiner Übergangsfunktion führt er nun eine der Operationen push, pop, oder nop (keine Operation) aus. Anschließend rückt der Lesekopf auf dem Eingabeband eine Position nach rechts zum nächsten Zeichen (R) oder bleibt stehen (H). Steht er auf dem Eingabeende, muss er stehen bleiben.

Hinweis: Analog zum Kurs Q1 muss auch hier darauf hingewiesen werden, dass Kellerspeicher unterschiedlich implementiert werden können. Hier liest pop das oberste Kellerzeichen k und entfernt dieses gleichzeitig aus dem Kellerspeicher. Möglich ist auch eine weitere Operation top, die lediglich das obere Kellerzeichen k liest. In diesem Fall ist es möglich, das oberste Kellerzeichen nur zu lesen, ohne es zu löschen ... z. B. das Kellerleerzeichen #.

Beispiel: Die Sprache $L=~\lbrace a^nb^n\vert n \in \mathbb{N}\rbrace$

Wir wollen uns nun an einem Beispiel die Arbeitsweise des Automaten ansehen. Wir konstruieren einen Automaten, der gerade die Sprache $L=~\lbrace a^nb^n\vert n \in \mathbb{N}\rbrace$ akzeptiert. Die Idee dazu ist einfach: Zuerst (... nach der Initialisierung ...) werden alle a's gelesen und in den Speicher kopiert. Bei jedem folgenden b wird dann ein a aus dem Speicher gelöscht. Wird das letzte a genau dann gelöscht, wenn das letzte b gelesen wurde, so hat das Eingabewort die gewünschte Gestalt und wird akzeptiert. In allen anderen Fällen wird es abgelehnt.

Die Überführungsfunktion kann folgendermaßen dargestellt werden:

zo a #  ->  push a zo
zo a a  ->  push a zo
zo b #  ->  nop zf
zo b a  ->  pop z1
z1 a #  ->  nop zf
z1 a a  ->  nop zf
z1 b #  ->  nop zf
z1 b a  ->  pop z1

Dabei bedeutet die Zeile z_o a # -> push a z_o: Der Automat befindet sich in Zustand z_o, liest ein a vom Eingabeband und der Keller ist leer (oberstes Zeichen ist das Kellerleerzeichen #); er speichert das gelesene Zeichen (a) im Keller ab und geht in den Folgezustand z_o über.

Die Darstellung (Reihenfolge der Attribute) der Überführungsfunktion kann unterschiedlich aussehen. Unsere Variante richtet sich u. a. an der Darstellung im Programm P_automat aus. Zudem gibt es unterschiedliche Notationsformen:

 zo a #  ->  push a zo
 (zo, a, #)  ->  (push(a), zo)
 $\delta$(zo, a, #) = (push(a), zo)

Man kann analog zu den Zustandsgraphen bei den Automaten auche einen Zustandsgraphen für Kellerautomaten angeben. Dabei kann man sich auf die vier Zustandsübergänge beschränken, die nicht in den Fehlerzustand führen.