# 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^{n}b^{n}c^{n} (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.