Pushdown Automaton

In computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.

The PDA is used in theories about what can be computed by machines. It is more capable than a finite-state machine but less capable than a Turing machine. Because its input can be described with a formal grammar, it can be used in parser design. The deterministic pushdown automaton can handle all deterministic context-free languages while the nondeterministic version can handle all context-free languages.

The term "pushdown" refers to the fact that the stack can be regarded as being "pushed down" like a tray dispenser at a cafeteria, since the operations never work on elements other than the top element. A stack automaton, by contrast, does allow access to and operations on deeper elements. Stack automata can recognize a strictly larger set of languages than deterministic pushdown automata. A nested stack automaton allows full access, and also allows stacked values to be entire sub-stacks rather than just single finite symbols.

The remainder of this article describes the nondeterministic pushdown automaton.