Push-down automaton

A push-down automaton (PDA) is a simple form of imaginary machine; essentially, it is a finite-state automaton hooked up to a unbounded stack onto which symbols can be pushed, and off of which symbols can subsequently be popped, in a last-in first-out order.

Push-down automata are more powerful than finite-state automata; for instance, the problem of recognizing that parentheses are correctly nested in a string can be solved by a PDA, but not by a FSA.

By the same token, there are certain strings which push-down automata are incapable of recognizing, such as aⁿbⁿcⁿ (that is, a number of a's, followed by the same number of b's followed by the same number of c's.) This makes PDAs less powerful than Turing machines.

A push-down automaton can be deterministic or nondeterministic, and unlike for FSAs, these are not equivalent in power. Deterministic PDAs can recognize the so-called LR(1) languages, while nondeterministic ones can recognize any context-free language.

See also

• A listing of esoteric languages on this site which have the same computational power as push-down automata.