Ein Kellerautomat ist eine Erweiterung des endlichen Automatens, welcher über einen Speicher verfügt.
Dadurch kann er auch kontextfreie Grammatiken darstellen.
Bei dem Speicher handelt es sich um einen Stack, wobei in jedem Schritt das oberste Element destruktiv ausgelesen wird.
Der Boden des Kellers ist durch das Zeichen # markiert.
In abhängigkeit des aktuellen Zustandes und der Position im Eingabewort(Zustand) und des obersten Kellersymbols, wechselt der Automat seinen Zustand und legt neue Symbole in den Keller. Der Automat akzeptiert ein Wort, wenn er wieder im Endzustand steht.
Definition
A = (Q, Σ, Γ, 𝛿, q0, #, F ) Q ist die Menge an Zuständen (endlich) Σ ist das Eingabealphabet Γ ist das Kelleralphabet (Eingabealphabet muss nicht = Kelleralphabet sein) q0 ist der Startzustand # ist das Zeichen, das einen auf einem leeren Stack zuweist F ist die Menge der Endzustände (Teilmenge von Q also auch endlich)
Schritte
- Wir lesen die Eingabe
- Wir lesen und zerstören das obere Stackelement
- Wir schreiben auf den Stack
- Wir wechseln den Zustand