Ein PDA ist ein Kellerautomat. Kellerautomaten können deterministisch oder nicht-deterministisch sein.
Ein DPDA ist ein deterministischer Kellerautomat. Das heißt zu jedem Tupel aus Zustand, Eingabezeichen und Kellerzeichen gibt es höchstens ein Tupel aus Zustand und Kellerwort. das angewendet werden kann.
