NPDAs

Non-deterministic pushdown automata (NPDAs) are a formal model of computation used to recognize context-free languages. Like ordinary pushdown automata, they have a finite set of states and a stack, but their transition relation is nondeterministic: from a given configuration the machine may pursue several possible moves in parallel.

An NPDA is typically defined as a 7-tuple (Q, Σ, Γ, δ, q0, Z0, F). Q is a finite set of states, Σ is the input alphabet, Γ is the stack alphabet, Z0 is the initial stack symbol, q0 ∈ Q is the start state, and F ⊆ Q is the set of accepting states. The transition relation δ is a subset of Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*). Informally, from state q reading input symbol a (which may be ε) with a top stack symbol X, the machine may move to state p and replace X by a (possibly empty) string α of stack symbols. This nondeterministic choice allows multiple computation paths to be explored simultaneously.

Acceptance of an input string can be defined by final state (ending in a state in F) or by empty stack, or by a combination of the two depending on the convention. Many sources show that these criteria are equivalent up to standard constructions, so NPDA definitions often allow either acceptance mode.

NPDAs characterize context-free languages: for every NPDA, the language it accepts is context-free, and for every context-free language there exists some NPDA that accepts it. Deterministic pushdown automata (DPDA) are a stricter form that recognize only deterministic context-free languages, a proper subset of CFLs; there exist CFLs not recognizable by any DPDA.