Ein Kellerautomat oder auch Push-Down-Automat (PDA, engl. pushdown automaton) ist ein Konstrukt der theoretischen Informatik.
Er besteht aus einem endlichen Automaten und einem Kellerspeicher.
Mit Hilfe eines PDAs können kontextfreie Sprachen erkannt werden. Sie sind damit mächtiger als endliche Automaten aber weniger mächtig als Turingmaschinen.
Definition
Ein PDA 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 K der Startzustand
- z0 Γ das Anfangssymbol im Keller
- F K eine Menge von finalen Zuständen
ist.
Beispiel
Gegeben sei die Sprache L = {anbn | 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
- δ(k0, a, z0) = {(k0, az0)}
- δ(k0, a, a) = {(k0, aa)}
- δ(k0, b, a) = {(k1, ε)}
- δ(k1, b, a) = {(k1, ε)}
- δ(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). 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.