Nondeterministic pushdown automata

Let $\mathrm{\Sigma }$ be an input alphabet. A nondeterministic pushdown automaton (PDA) over $\mathrm{\Sigma }$ is a septuple $M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,Z_0,F)$ such that:

• $Q$ is a finite set of states.
• $\mathrm{\Gamma }$ is a finite stack alphabet.
• $q_0\in Q$ is the start state.
• $Z_0\in \mathrm{\Gamma }$ is the initial stack symbol.
• $F\subseteq Q$ is the set of accepting states.
• $\delta$ assigns to each triple $(q,x,Z)\in Q\times (\mathrm{\Sigma }\cup \{\epsilon \})\times \mathrm{\Gamma }$ a finite set of pairs $(p,\beta )\in Q\times {\mathrm{\Gamma }}^{\ast }$.

The intended meaning of $(p,\beta )\in \delta (q,x,Z)$ is that, when the machine is in state $q$ with top stack symbol $Z$, it may read $x$ if $x\in \mathrm{\Sigma }$ or read nothing if $x=\epsilon$, pop $Z$, replace it by the word $\beta$, and move to state $p$.

• The stack is the extra memory absent from finite automata.

• Nondeterminism means that several pairs $(p,\beta )$ may be enabled from the same triple $(q,x,Z)$.