Pushdown automaton

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.