In computer science, pushdown automata (PDA) are abstract devices defined in automata theory that recognize context-free languages.
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. Non-deterministic pushdown automata (NPDA) are more potent than deterministic pushdown automata: there exist languages that are recognized by some non-deterministic pushdown automaton but that cannot be recognized by any deterministic pushdown automaton.
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 - we obtain the equivalent to a Turing machine.
A NPDA W can be defined as a 7-tuple function:
where