Pushdown automata differ from normal finite state machines in two ways:
Pushdown automata choose a transition by indexing a table by input signal, current state, and the top of the stack. Normal finite state machines just look at the input signal and the current state: they have no stack to work with. Pushdown automata add the stack as a parameter for choice. Given an input signal, current state, and a given symbol at the top of the stack, a transition path is chosen. Pushdown automata can also manipulate the stack, as part of performing a transition. Normal finite state machines choose a new state, the result of following the transition. The manipulation can be to push a particular symbol to the top of the stack, or to pop off the top of the stack. The automaton can alternatively ignore the stack, and leave it as it is. The choice of manipulation (or no manipulation) is determined by the transition table.
| 
Put together: Given an input signal, current state, and stack symbol, the automaton can follow a transition to another state, and optionally manipulate (push or pop) the stack. In general pushdown automata may have several computations on a given input string, some of which may be halting in accepting configurations while others are not. Thus we have a model which is technically known as a "nondeterministic pushdown automaton" (NPDA). Thus, nondeterminism means that there may be more than just one transition available to follow, given an input signal, state, and stack symbol. If in any situation only one transition is available as continuation of the computation, then the result is a deterministic pushdown automaton (DPDA), a strictly weaker device |
