PushdownAutomaten

Pushdownautomaten, in English Pushdown Automata, are a class of abstract machines used in formal language theory to recognize context-free languages. A pushdown automaton extends a finite automaton with a stack, enabling it to store an unbounded amount of information symbolically. A typical PDA consists of a finite set of states, an input alphabet, a stack alphabet, a transition function, a start state, an initial stack symbol and a set of accepting states (or an acceptance condition by empty stack). The transition function maps a current state, an input symbol (or ε for empty), and the symbol on the top of the stack to a set of possible new states and stack operations (push, pop, or replace). Because the transition relation is often nondeterministic, a PDA may have several computation paths for a given input.

There are nondeterministic and deterministic variants. Nondeterministic pushdown automata can recognize exactly the class of context-free languages. Deterministic pushdown automata recognize the deterministic context-free languages, a proper subset of CFLs. PDA languages are closed under union, concatenation and Kleene star, but not under intersection or complement in general.

PDA are equivalent in expressive power to context-free grammars: for every PDA there is a context-free grammar generating the same language, and vice versa. They are central to parsing and compiler design, where context-free grammars define most programming language syntax. A simple example is the language of balanced parentheses: strings with proper nesting.

History: Pushdown automata were developed in the 1960s as a formal model for parsing and language recognition, building on finite automata with an auxiliary memory structure.