Pushdown automata are abstract devices defined in
automata theory. They are similar to
finite automata, except that they have
access to a potentially unlimited amount of memory in the form of a single
stack. Pushdown automata exist in deterministic and non-deterministic varieties, and the two are not equipotent. Every pushdown automaton accepts a
formal language. The languages accepted by the non-deterministic pushdown automata are precisely the
context-free languages.
If we allow a finite automaton access to two stacks instead of just one, we obtain a device much more powerful than a pushdown automaton: it is equivalent to a Turing machine.