|
A non-deterministic pushdown automaton (or PDA) is a variation on the idea of a non-deterministic finite automaton (NDFA). Unlike an NDFA, a PDA is associated with a stack (hence the name pushdown). The transition function must also take into account the state of the stack.
Formally defined, a non-deterministic pushdown automaton is a 6-tuple
 .
 and  are the same as for an NDFA.  is the stack alphabet, specifying the set of symbols that can be pushed onto the stack. The transition function is
 Like an NDFA, a PDA can be presented visually as a directed graph, called a state diagram. Instead of simply labelling edges representing transitions with the leading symbol, two additional symbols are added, representing what symbol must be matched and removed from the top of the stack (or  if none) and what symbol should be pushed onto the stack (or  if none). For instance, the notation a A/B for an edge label indicates that a must be the first symbol in the remaining input string and A must be the symbol at the top of the stack for this transition to occur, and after the transition, A is replaced by B at the top of the stack. If the label had been
 , then the symbol at the top of the stack would not matter (the stack could even be empty), and B would be pushed on top of the stack during the transition. If the label had been
 , A would be popped from the stack and nothing would replace it during the transition.
When a PDA halts, it is considered to have accepted the input string if and only if there is some final state where the entire input string has been consumed and the stack is empty.
For example, consider the alphabet
 . Let us define a context-free language  that consists of strings where the parentheses are fully balanced. If we define
 , then a PDA for accepting such strings is:
Another simple example is a PDA to accept binary palindromes (that is,
 ).
It can be shown that the language of strings accepted by any PDA is a context-free language, and that any context-free language can be represented by a PDA.
| 
![$\displaystyle \UseComputerModernTips \xymatrix{ \ar[r] & *++[o][F=]{0} \ar@(u,... ...\texttt{(}\,\lambda/\texttt{A}} \ar@(d,r)[]_{\texttt{)}\,\texttt{A}/\lambda} } $](http://images.planetmath.org:8080/cache/objects/2571/l2h/img13.png "$\displaystyle \UseComputerModernTips \xymatrix{ \ar[r] & *++[o][F=]{0} \ar@(u,... ...\texttt{(}\,\lambda/\texttt{A}} \ar@(d,r)[]_{\texttt{)}\,\texttt{A}/\lambda} } $")
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ \ar[r] & *+[o][F-]{0} \ar@(u,r)[... ...++[o][F=]{1} \ar@(u,r)[]^{0\,A/\lambda} \ar@(d,r)[]_{1\,B/\lambda} } } \end{xy}$](http://images.planetmath.org:8080/cache/objects/2571/l2h/img15.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ \ar[r] & *+[o][F-]{0} \ar@(u,r)[... ...++[o][F=]{1} \ar@(u,r)[]^{0\,A/\lambda} \ar@(d,r)[]_{1\,B/\lambda} } } \end{xy}$")