|
|
|
Viewing Version
8
of
'non-deterministic pushdown automaton'
|
[ view 'non-deterministic pushdown automaton'
|
back to history
]
| Title of object: |
non-deterministic pushdown automaton |
| Canonical Name: |
PushdownAutomaton |
| Type: |
Definition |
| Created on: |
2002-02-24 02:46:57 |
| Modified on: |
2009-05-11 02:20:28 |
| Classification: |
msc:68Q05, msc:68Q42, msc:03D10 |
| Defines: |
state diagram, stack alphabet, start stack symbol |
| Synonyms: |
non-deterministic pushdown automaton=pushdown automaton
non-deterministic pushdown automaton=PDA
non-deterministic pushdown automaton=NPDA
non-deterministic pushdown automaton=initial stack symbol |
Preamble:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage[all]{xy} |
Content:
\PMlinkescapeword{name}
\PMlinkescapeword{onto}
\PMlinkescapeword{simple}
A \emph{non-deterministic pushdown automaton} (NPDA), or just \emph{pushdown automaton} (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 \textit{pushdown}). The transition function must also take into account the ``state'' of the stack.
Formally defined, a pushdown automaton $M$ is a 7-tuple $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 \emph{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 \emph{start stack symbol}. The transition function is $$T : Q\times(\Sigma\cup\{\lambda\})\times\Gamma\to\mathcal{P}(Q \times \Gamma^*).$$
To see how $M$ works, first imagine $M$ with a finite set $Q$ of internal states, equipped with a horizontal tape of cells each containing an input symbol of $\Sigma$, and a vertical stack of cells each storing a symbol of $\Gamma$:
\begin{itemize}
\item given that $M$ is in state $p$ reading input symbol $a$, with symbol $A$ on top of the stack, it can ``pop'' $A$ off the stack, and ``push'' a word $B$ over $\Gamma$ onto the stack, move the read head to the right of the cell containing $a$, and enter state $q$, as long as $(q,B)\in T(p,a,A)$
\item given that $M$ is in state $p$, with symbol $A$ on top of the stack, it can ``pop'' $A$ off the stack, and ``push'' a word $B$ over $\Gamma$ onto the stack, and enter state $q$, as long as $(q,B)\in T(p,\lambda,A)$.
\end{itemize}
Like an NDFA, a PDA can be presented visually as a directed graph, called a \emph{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
\verb=a A/B= for an edge label indicates that \verb=a= must be the first symbol in the remaining input string and \verb=A= must be the symbol at the top of the stack for this transition to occur, and after the transition, \verb=A= is replaced by \verb=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 \verb=B= would be pushed on top of the stack during the transition. If the label had been $\verb=a=\,\verb=A/=\lambda$, \verb=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 \emph{and} the stack is empty.
For example, consider the alphabet $\Sigma := \left\{ \verb=(=, \verb=)= \right\}$.
Let us define a context-free 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}
}
$$
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. |
|
|
|
|
|
