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. Some deterministic pushdown automata cannot accept context-free languages that can be accepted by non-deterministic pushdown automata.

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.