Kellerautomat

Ein Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der theoretischen Informatik, ein Konstrukt, das verwendet wird, um gewisse Eigenschaften von Problemen und Algorithmen zu analysieren und zu beweisen.

Der Kellerautomat ist ein endlicher Automat, der um einen Kellerspeicher (a.g. Stack) erweitert wurde. Ein Kellerautomat mit zwei Kellerspeichern ist gleichmächtig zur Turingmaschine.