Kellerautomat

Ein Kellerautomat oder auch Pusch-Down-Automat (PDA, engl. pushdown automaton) ist ein Konstrukt der theoretischen Informatik mit wenigen realen Implementierungen. 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. Ein PDA wird definiert als ein Tupel

M=(K,Sigma,Gamma,Delta,s0,Z0,F)

wobei

• K eine endliche Menge von Zuständen
• Sigma ein Eingabealphabet
• Gamma das Kelleralphabet
• Delta die Zustandsübergangsrelation, eine endliche Teilmenge von (K x (Sigma vereinigt {epsilon}) x Gamma) x (K x Gamma*)
• s0 element K der Startzustand
• Z0 element Gamma das Anfangssymbol im Keller
• F teilmenge K eine Menge von finalen Zuständen

ist.