Kellerautomat

Ein Kellerautomat (auch PDA für engl. pushdown automaton) ist ein Konstrukt der theoretischen Informatik. Er besteht aus einem endlichen Automaten und einem Kellerspeicher. Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur Turingmaschine.

Der nichtdeterministische Kellerautomat erkennt genau die kontextfreien Sprachen. Sie sind damit mächtiger als endliche Automaten, welche genau die regulären Sprachen erkennen, aber weniger mächtig als Turingmaschinen, welche genau die rekursiv aufzählbaren Sprachen erkennen.

Definition

Ein Kellerautomat wird definiert als ein 7-Tupel M=(K,Σ,Γ,δ,s0,z0,F)

wobei

• K eine endliche Menge von Zuständen
• Σ ein Eingabealphabet
• Γ das Kelleralphabet
• δ die Zustandsübergangsrelation, eine endliche Teilmenge von (K × (Σ ∪ {ε}) × Γ) × (K × Γ*)
• s0$\in$K der Startzustand
• z0$\in$Γ das Anfangssymbol im Keller
• F$\subseteq$K eine Menge von finalen Zuständen

ist.

Beispiel

Gegeben sei die Sprache L = {aⁿbⁿ | n > 0}. Wörter der Sprache sind also beispielsweise aabb oder auch aaabbb.

Der folgender Kellerautomat M erkennt nun die Sprache L:

M=(K,Σ,Γ,δ,s0,z0,F)

mit

K = {k0, k1, k2}
Σ = {a,b}
Γ = {z0,a,b}
s0 = {k0}
z0 = {z0}
F = {z2}

und der Überführungsfunktion

1. δ(k0, a, z0) = {(k0, az0)}
   
2. δ(k0, a, a) = {(k0, aa)}
   
3. δ(k0, b, a) = {(k1, ε)}
   
4. δ(k1, b, a) = {(k1, ε)}
   
5. δ(k1, ε, z0) = {(k2, ε)}
   .
   

Die erste Zeile bedeutet: Wenn der jetzige Zustand k0 ist, das dabei eingelesene Zeichen a ist, und das oberste Zeichen des Kellers z0 ist, dann wird der Zustand beibehalten, und a auf z0 in den Keller geschrieben (a ist jetzt das oberste Zeichen und direkt darunter befindet sich z0). Durch die zweite Zeile wird immer wieder ein a auf den Kellerspeicher geschrieben. Erreicht der Schreib-Lesekopf schließlich das Zeichen b, so wird der Zustand gewechselt, und das a wird vom Keller gelöscht (ε = leeres Wort). Wenn der Ausdruck abgearbeitet wurde, und im Kellerspeicher wieder z0 steht, so wird z0 gelöscht, und in den Endzustand z2 übergegangen. D.h. der Ausdruck wurde komplett gelesen, und somit erfolgreich abgearbeitet.