Kellerautomaten

Bei einem Kellerautomaten handelt es sich um einen endlichen Automaten, der um einen Kellerspeicher erweitert wurde. Nichtdeterminitische Kellerautomaten lösen das Wortproblem für die Klasse der kontextfreien Sprachen. Das bedeutet, dass Kellerautomaten genau die Sprachen erkennen können, die eine kontextfreie Grammatik besitzen.

Was den regulären Sprachen die endlichen Automaten sind, sind den kontextfreien Sprachen die Kellerautomaten.

Funktionsweise 

Die zugrundeliegende Idee beim Kellerautomaten ist die folgende: Die Eingabe wird zeichenweise von links nach rechts verarbeitet. Wenn es möglich ist, wird das Eingabezeichen sofort verarbeitet, wenn nicht, wird es in den Kellerspeicher gelegt und die Bearbeitung sobald wie möglich nachgeholt. Die möglichen Aktionen des Automaten hängen dabei, wie beim endlichen Automaten, vom momentan verarbeiteten Eingabezeichen, vom momentanen Zustand des Automaten und (das ist die Erweiterung gegenüber dem endlichen Automaten) zusätzlich vom Kellerinhalt ab, wobei immer nur das oberste Zeichen des Kellers relevant ist. In jedem Verarbeitungsschritt (das Lesen eines Zeichens und die damit zusammenhängenden Operationen) kann sich der Zustand des Automaten und der Kellerinhalt ändern.

Formale Definition

Ein nichtdeterministischer Kellerautomat ist ein 7-Tupel M = {Q, Σ, Γ, δ, q₀, k₀, E}.

• Q ist eine endliche Menge von Zuständen.
• Σ ist ein Alphabet, das sog. Eingabealphabet.
  
• Γ ist eine Alphabet, das sog. Kelleralphabet
• δ ⊆ Q × Γ × (Σ ∪ {ε}) × Q × Γ^* ist die Übergangsrelation.
  
• q₀ ∈ Q ist der Startzustand.
• k₀ ∈ Γ ist Kellerleerzeichen, auch Kellerstartsymbol (in der Regel #).
• E ⊆ Q ist die Menge der Endzustände.
  [Alternativ gibt es auch die Möglichkeit, Eingaben "mit leerem Keller" zu akzeptieren. Das bedeutet, dass eine Eingabe akzeptiert wird, wenn nach ihrer Abarbeitung der Keller leer ist]
  

δ als Relation
Der Automat wird als nicht-deterministisch definiert, d.h. von einem Zustand aus sind bei identischem Eingabe- und Kellerzeichen verschiedene Folgezustände möglich. Das hat zur Folge, dass man δ nicht mehr als einfache Funktion (= linkseindeutige Relation) definieren kann. Ein und demselben Eingabetripel Q × Γ × (Σ ∪ {ε}) können nun mehrere verschiedene Ausgabetupel Q × Γ^* zugeordnet sein. Aus diesem Grund definiert man δ nun allgemeiner als Relation, also als Teilmenge des kartesischen Produktes Q × Γ × (Σ ∪ {ε}) × Q × Γ^*.

ε-Übergänge
Die Schreibweise Σ ∪ {ε} bedeutet, dass sogenannte ε-Übergänge zulässig sind. Das bedeutet, dass der Kellerautomat in einem Verabreitungsschritt statt dem nächsten Eingabezeichen auch "nichts" lesen kann. Das Eingabeband bleibt in diesem Fall stehen und wird nicht wie sonst vorgerückt. Der Automat generiert seine Ausgabe (Zustandswechsel, Kellerwort) nur aufgrund seines aktuellen Zustands und des obersten Kellerzeichens.

Beispiel 

Um das Prinzip eines Kellerautomaten zu verdeutlichen, betrachten wir die Sprache der "wohlgeformten Klammerterme".

Der Automat beginnt in einem Startzustand q₀; 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 (Akzeptieren mit leerem Keller). 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.

Graphen von Kellerautomaten 

Wir betrachten das Beispiel eines Kellerautomaten, der die Sprache L = {aⁿbⁿ | n>0} akzeptiert. Der Kellerautomat ist gegeben durch

• Q = {q₀, q₁, q₂}.
• Σ = {a, b).
  
• Γ = {#, A, B}.
• δ = {(q₀, #, a, q₀, A#), (q₀, A, a, q₀, AA), (q₀, A, b, q₁, ε), (q₁, A, b, q₁, ε), (q₁, #, $, q₂, #)}.
  
• q₀ = q₀.
• k₀ = #.
• E = {q₂}.

Wir haben es hier mit einem deterministischen Kellerautomaten zu tun! Es gibt genau einen ε-Übergänge in den Endzustand q₂.

Der Graph zu diesem Kellerautomaten sieht folgendermaßen aus:

Der Unterschied zum Graphen eines endlichen Automaten besteht zum einen darin, dass die Zustandsübergangsfunktion neben dem aktuellen Zustand und dem nächsten Eingabezeichen (Ausnahme: ε-Übergänge) auch das oberste Kellerzeichen benötigt. Zum anderen bewirkt die Übergangsfunktion neben dem Zustandswechsel auch das Schreiben eines Kellerwortes in den Keller.

• (A, a) : AA  : Das erste Zeichen in der Klammer (hier: 'A') steht für das Kellerzeichen, das aktuell im Keller ganz oben liegt.
• (A, a) : AA  :  Das zweite Zeichen in der Klammer (hier: 'a') steht für das nächste Eingabezeichen.
• (A, a) : AA  : Hinter dem Doppelpunkt steht das Kellerwort (hier 'AA'), dass in den Keller gespeichert wird.
  

Weitere Erläuterungen zum Graphen und zur Abarbeitung einer Eingabe:

• Vom Zustand q₀ gehen oben 3 Pfeile aus. Einer führt nach q₁, zwei wiederum nach q₀.Der Übergang mit der Beschriftung (#, A) : A# bewirkt, dass, wenn der Keller noch leer ist und das erste a gelesen wird, ein A in den Keller gespeichert wird. Beim Lesen wird # aus dem Keller entfernt, deshalb muss das Kellerleerzeichen ebenfalls wieder in den Keller gelegt werden. Das Kellerwort wird von rechts nach links zeichenweise im Keller gespeichert.
• Solange nun weitere a's im Eingabewort folgen, wird im Graphen immer wieder der Verbindung mit der Bezeichnung (A, a) : AA gefolgt. Will heissen: Wenn oben im Keller ein A liegt (beim Nachsehen wird gelöscht!) und ich ein weiteres a als nächstes Eingabezeichen finde, schreibe ich zwei A's ('AA') in den Kellerspeicher.
  
• Sobald das erste b kommt, folgen wir dem Pfeil zum Zustand q₁. Ein ε als Kellerwort bedeutet, dass in diesem Schritt "nichts" in den Keller geschrieben wird. Da man zuvor das oberste Zeichen gelesen hat und es nun nicht wieder zurückschreibt, kommt diese Angabe einer Löschung des obersten Zeichens gleich.
• Schließlich folgen wir nun solange dem Pfeil mit der Bezeichnung (A,b) : ε wie wir noch b's im Eingabewort finden.
  
• Wenn aus dem Zustand q₁ heraus das Kellerzeichen # lesen, gelangen wir per ε-Übergang in den Endzustand q₂. Wenn gleichzeitig auch das Ende der Eingabe erreicht ist, ist das Eingabewort ist akzeptiert. Wenn noch ein Zeichen auf dem Eingabeband steht, verursacht dieses im nächsten Verarbeitungsschritt einen Fehler, da es aus q₂ heraus nicht mehr verarbeitet werden kann!

Kontextfreie Grammatiken und Kellerautomaten

Zu jeder kontextfreien Grammatik gibt es einen äquivalenten (nichtdeterministischen!) Kellerautomaten und umgekehrt. Dies bedeutet also, dass die Klasse der kontextfreien Sprachen genau die Klasse der Sprachen ist, die sich von (nichtdeterministischen) Kellerautomaten erkennen lassen.

Im Folgenden wird ein konstruktives Verfahren dafür angegeben, wie man im Allgemeinen aus einer gegebenen kontextfreien Grammatik einen nichtdeterministischen Kellerautomaten gewinnt.

Wir betrachten dazu das Beispiel der wohlgeformten Klammerterme mit der Grammatik G = {N = {S}, Σ = {(, )}, P = {S → () | (S) | SS}, S = S}.

Der Kellerautomat zur kontextfreien Sprache der Klammerterme ist folgendermaßen definiert:

• Q = {z₀}. [Der aus diesem Verfahren resultierende Kellerautomat hat immer nur einen Zustand]
  
• Σ = {(, )). [Das Eingabealphabet entspricht gerade der Menge der Terminalsymbole)
  
• Γ = N ∪ Σ = {S, (, )}. [Das Kelleralphabet enthält alle Nicht-Terminalsymbole und alle Terminalsymbole]
  
• q₀ = z₀.
• k₀ = S. [Das Kellerleerzeichen ist gleich dem Startsymbol der Grammatik]
  
• E = ∅. [Ein Eingabewort wird akzeptiert, falls der Keller nach Abarbeitung des Wortes leer ist.]
  

Bleibt noch die Übergangsrelation, die nach zwei Regeln gebildet wird:

1. Ist das gelesene Kellerzeichen ein Terminalsymbol [hier ( oder )] , so wird geprüft, ob das aktuelle Eingabezeichen mit dem Kellerzeichen übereinstimmt. Ist dies der Fall, so wird das Kellerzeichen gelöscht und zum nächsten Eingabezeichen übergegangen. Daraus folgen die Übergänge

   δ₁ = (z₀, (, (, z₀, ε) und
   δ₂ = (z₀, ), ), z₀, ε).

2. Ist das gelesene Kellerzeichen ein Nichtterminalsymbol (hier S), so wird kein Eingabezeichen gelesen und das Kellerzeichen S wird durch die rechte Seite einer Regel, also () oder (S) oder SS ersetzt. Es ergibt sich:

   δ₃ = (z₀, S, ε, z₀, ()) und
   δ₄ = (z₀, S, ε, z₀, SS) und
   δ₅ = (z₀, S, ε, z₀, (S)).

Insgesamt folgt:

 δ = {(z₀, (, (, z₀, ε), (z₀, ), ), z₀, ε), (z₀, S, ε, z₀, ()), (z₀, S, ε, z₀, SS), (z₀, S, ε, z₀, (S))}.

Das sieht dann als Graph so aus:

Dieser Kellerautomat ist zum einen nichtdeterministisch und zum anderen enthält er drei ε-Übergänge! Der Kellerautomat akzeptiert die Sprache der Klammerterme mit leerem Keller. Seine Arbeitsweise lässt sich am besten mit Hilfe einer Tabelle nachvollziehen:

» drucken: pdf | html