Kellerautomat (KA) , Definition

Ein Kellerautomat (nachfolgend als KA bezeichnet) ist ein 7-Tupel, bestehend aus:

• Z: eine endliche Menge von Zuständen
• E: ein Eingabealphabet (daraus besteht der Strom von Eingabezeichen)
• K: ein Kelleralphabet    (werden mit push und pop bearbeitet)
• Z₀ Î Z: ein Anfangszustand
• K₀ Î K: ein Kellerstartsymbol
• M Î Z: eine endliche Menge von Endzuständen
• eine Übergangsfunktion f: (z_i Î Z; e_j Î E; k_n Î K) à (Z_m Î Z; K^* Ì K)

so arbeitet der Automat:

Nach Abarbeiten des Eingabebandes gilt: Wenn der KA sich in einem akzeptierenden Zustand befindet und auf dem Keller nur noch das Kellerstartsymbol liegt (= Keller ist leer), dann hat der KA die Zeichenfolge des Eingabebandes akzeptiert.