NPDA

NPDA stands for nondeterministic pushdown automaton. It is a theoretical model of computation that extends a finite automaton with a stack, giving it memory that can be used to recognize context-free languages. An NPDA consists of a finite set of states, an input alphabet, a stack alphabet, a start state, a start stack symbol, and a set of accepting states. The transition relation maps a current state, an input symbol (or epsilon), and the symbol at the top of the stack to one or more possible next states and pushdown actions (which may push or pop symbols). Because transitions can be chosen nondeterministically, there may be many possible computations from a given configuration.

An NPDA can accept a string by either of two common modes. In acceptance by final state, the machine must consume the entire input and reach an accepting state. In acceptance by empty stack, the machine must consume the entire input and end with an empty stack. Some definitions use a bottom-of-stack marker, in which case the empty-stack condition is interpreted accordingly. The nondeterministic nature means that if there exists at least one computation that leads to acceptance, the string is accepted.

NPDAs are equivalent in expressive power to context-free grammars: every context-free language can be recognized by an NPDA, and every language recognized by an NPDA is context-free. This contrasts with deterministic pushdown automata (DPDA), which recognize only a proper subset of context-free languages. Certain CFLs, such as those requiring nondeterministic guessing of a middle point (for example, palindromes), cannot be recognized by a DPDA.