You are here
Homenondeterministic pushdown automaton
Primary tabs
nondeterministic pushdown automaton
Definition
A nondeterministic pushdown automaton (NPDA), or just pushdown automaton (PDA) is a variation on the idea of a nondeterministic 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 pushdown automaton $M$ is a 7tuple $M=(Q,\Sigma,\Gamma,T,q_{0},\bot,F)$, where $Q,\Sigma,q_{0},$ and $F$, like those in an NDFA, are the set of states, the input alphabet, the start state, and the set of final states respectively. $\Gamma$ is the stack alphabet, specifying the set of symbols that can be pushed onto the stack. $\Gamma$ is not necessarily disjoint from $\Sigma$. $\bot$ is an element of $\Gamma$ called the start stack symbol. The transition function is
$T:Q\times(\Sigma\cup\{\lambda\})\times\Gamma\to\mathcal{P}(Q\times\Gamma^{*}).$ 
How It Works
To see how the computing machine $M$ works, first imagine $M$ with the following features:
1. a finite set $Q$ of internal states,
2. a horizontal tape of cells each containing an input symbol of $\Sigma$,
3. a tape reader that reads at most one tape cell in any given internal state, and
4. a vertical stack of cells storing symbols of $\Gamma$.
Now, given that $M$ is in state $p$, with symbol $A$ on top of the stack, and tape reader pointing at a tape cell containing symbol $a$, it may do one of the following:

if $T(p,a,A)\neq\varnothing$, then it
(a) “pops” $A$ off the stack,
(b) “pushes” word $A_{1}\cdots A_{n}$ onto the stack, by starting with symbol $A_{n}$, and ending with symbol $A_{1}$,
(c) “consumes” $a$ by moving the tape reader to the right of the cell containing $a$, and
(d) enters state $q$,
provided that $(q,A_{1}\cdots A_{n})\in T(p,a,A)$; if $T(p,a,A)=\varnothing$, then $M$ does nothing.

if $T(p,\lambda,A)\neq\varnothing$, then, without reading $a$, it
(a) “pops” $A$ off the stack,
(b) “pushes” word $A_{1}\cdots A_{n}$ onto the stack, and
(c) enters state $q$,
as long as $(q,A_{1}\cdots A_{n})\in T(p,\lambda,A)$; if $T(p,\lambda,A)=\varnothing$, then $M$ does nothing.
If $(q,\lambda)\in T(p,a,A)$, then $A$ gets popped off, and nothing gets pushed onto the stack.
Modes of Acceptance
A PDA is a language acceptor. We describe how words are accepted by a PDA $M$. First, we start with configurations.
A configuration of $M$ is an element of $Q\times\Sigma^{*}\times\Gamma^{*}$. For any word $u$, the configuration $(q_{0},u,\bot)$ is called the start configuration of $u$. A binary relation $\vdash$ on the set of configurations is defined as follows: if $(p,u,\alpha)$ and $(q,v,\beta)$ are configurations of $M$, then
$(p,u,\alpha)\vdash(q,v,\beta)$ 
provided that $\alpha=A\gamma$ and $\beta=B_{1}\cdots B_{n}\gamma$, for some $A,B_{1},\ldots,B_{n}\in\Gamma$, and

either $u=av$, and $(q,B_{1}\cdots B_{n})\in T(p,a,A)$,

or $u=v$, and $(q,B_{1}\cdots B_{n})\in T(p,\lambda,A)$.
Now, take the reflexive transitive closure $\vdash^{*}$ of $\vdash$. When $(p,u,\alpha)\vdash^{*}(q,v,\beta)$, we say that $v$ is derivable from $u$. A word $u\in\Sigma^{*}$ is said to be

accepted on final state by $M$ if $(q_{0},u,\bot)\vdash^{*}(q,\lambda,\alpha)$ for some final state $q\in F$,

accepted on empty stack by $M$ if $(q_{0},u,\bot)\vdash^{*}(q,\lambda,\lambda)$,

accepted on final state and empty stack by $M$ if $(q_{0},u,\bot)\vdash^{*}(q,\lambda,\lambda)$ for some $q\in F$.
Languages Accepted by a PDA
Given a mode of acceptance, the set of words accepted by $M$ is called the language accepted by $M$ based on that mode of acceptance. Given a PDA $M$, there are three languages accepted by $M$, corresponding to the three acceptance modes above.
It turns out that three modes of acceptance are equivalent, in the following sense: if a language $L$ is accepted by $M$ on one acceptance mode, there are PDA $M_{1}$ and $M_{2}$ that accept $L$ in the other two acceptance modes.
In general, unless otherwise stated, the language $L(M)$ accepted by a PDA $M$ stands for the language accepted by $M$ on final state.
Remarks.
1. Two PDAs are said to be equivalent if they accept the same language. It can be shown that any PDA is equivalent to a PDA where $T(p,\lambda,A)=\varnothing$ for all $p\in F$ and $A\in\Gamma$ (called a $\lambda$free PDA).
2.
Representation by State Diagrams
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 $\lambda$ if none) and what symbol should be pushed onto the stack (or $\lambda$ 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
$\verb=a=\,\lambda\verb=/B=$, 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 $\verb=a=\,\verb=A/=\lambda$, A
would be popped from the stack and nothing would replace it during the transition.
For example, consider the alphabet $\Sigma:=\left\{\verb=(=,\verb=)=\right\}$. Let us define a contextfree language $L$ that consists of strings where the parentheses are fully balanced. If we define $\Gamma:=\left\{A\right\}$, then a PDA for accepting such strings is:
$\UseComputerModernTips\xymatrix{\ar[r]&*++[o][F=]{0}\ar@(u,r)[]^{{\texttt{(}\,% \lambda/\texttt{A}}}\ar@(d,r)[]_{{\texttt{)}\,\texttt{A}/\lambda}}}$ 
Another simple example is a PDA to accept binary palindromes (that is, $\left\{w\in\left\{0,1\right\}^{*}\mid w=w^{R}\right\}$).
$\xymatrix{\ar[r]&*+[o][F]{0}\ar@(u,r)[]^{{0\,\lambda/A}}\ar@(d,r)[]_{{1\,% \lambda/B}}\ar[rrrr]^{{\stackrel{\lambda\,\lambda/\lambda}{\stackrel{0\,% \lambda/\lambda}{\stackrel{1\,\lambda/\lambda}{}}}}}&&&&*++[o][F=]{1}\ar@(u,r)% []^{{0\,A/\lambda}}\ar@(d,r)[]_{{1\,B/\lambda}}}$ 
Mathematics Subject Classification
03D10 no label found68Q42 no label found68Q05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections