Pushdown automaton

In particular automata theory, pushdown automata (PDA) are abstract devices that recognize context-free languages.

Informally, a pushdown automaton is a finite automaton outfitted with access to a potentially unlimited amount of memory in the form of a single stack. The finite automaton in question is usually a nondeterministic finite state machine (resulting in a nondeterministic pushdown automaton or NPDA) since deterministic pushdown automata cannot recognize all context-free languages.

If we allow a finite automaton access to two stacks instead of just one, we obtain a more powerful device — equivalent in power to a Turing machine. A linear bounded automaton is a device which is more powerful than a pushdown automaton but less so than a Turing machine.

A NPDA W can be defined as a 7-tuple:

$W = (Q,Σ,Φ,σ, s,Ω, F)$ 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 \times ( \Sigma \cup \left \{ \epsilon \right \} ) \times \Phi) \longrightarrow ( Q \times \Phi ^{*} )$
$s$ is an element of $Q$ the start state
$Ω$ is the initial stack symbol
$F$ is subset of $Q$ , consisting of the final states.

There are two possible acceptance criteria: acceptance by empty stack and acceptance by final state. The two are easily shown to be equivalent: a final state can perform a pop loop to get to an empty stack, and a machine can detect an empty stack and enter a final state by detecting a unique symbol pushed by the initial state.

Pushdown automaton

See also