Main Page | See live article | Alphabetical index 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 Q is a finite set of states Σ is a finite set of the input alphabet Φ is a finite set of the stack alphabet σ is a finite transition relation (Q × ( Σ & {ε}) × Φ) × ( Q × Φ* ) s is an element of Q; the start state Ω is the inital stack symbol F is subset of Q, consisting of the final states. This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.