Pushdown

Pushdown refers to a model of computation known as a pushdown automaton (PDA), an automaton equipped with a stack (pushdown store). It extends finite automata by adding a last-in-first-out storage, enabling it to recognize a broader class of languages known as context-free languages.

A PDA consists of a finite set of states, an input alphabet, a stack alphabet, a transition function, a start state, and a set of accept states or an acceptance condition by empty stack. At each step, it reads an input symbol (or epsilon), reads the symbol on top of the stack, and may push symbols onto or pop symbols from the stack. The machine accepts an input when it ends in an accept state or when the stack meets the chosen acceptance criterion.

Two main variants exist: nondeterministic PDA (NPDA) and deterministic PDA (DPDA). NPDA can have multiple possible moves from a given configuration, while DPDA has at most one legal move for each configuration. NPDAs recognize all context-free languages; DPDAs recognize exactly the deterministic context-free languages, which cover many programming language constructs but not all CFLs.

Pushdown automata are equivalent in language recognition power to context-free grammars: for every PDA there is a context-free grammar generating the same language, and conversely. In practice, PDAs underpin parsing theory, and numerous parsing approaches, such as those used in compilers, are designed to simulate deterministic pushdown automata.

Pushdown storage is also used in programming language runtimes to implement mechanisms like function calls and expression evaluation via stacks. While powerful for context-free structures, pushdown automata are weaker than Turing machines and cannot recognize non-context-free languages.