next up previous
Next: How does a PDA Up: Pushdown automata Previous: Pushdown automata

What is a pushdown automaton?

A pushdown automaton $ P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ is given by the following data

As an example we consider a PDA $ P$ which recognizes the language of even length palindromes over $ \Sigma=\{0,1\}$ -- $ L=\{ww^R \mid w
\in \{0,1\}^*\}$. Intuitively, this PDA pushes the input symbols on the stack until it guesses that it is in the middle and then it compares the input with what is on the stack, popping of symbols from the stack as it goes. If it reaches the end of the input precisely at the time when the stack is empty, it accepts.

$\displaystyle {P_0} = (\{ q_0,q_1,q_2 \}, \{0,1\},\{0,1,\char93 \},\delta,q_0,\char93 ,\{q_2\})
$

where $ \delta$ is given by the following equations:

\begin{displaymath}
\begin{array}{lcl}
\delta(q_0,0,\char93 ) & = & \{(q_0,0\cha...
...a(q,w,z) & = & \{\} \qquad \textrm{everywhere else}
\end{array}\end{displaymath}

To save space we may abbreviate this by writing:

\begin{displaymath}
\begin{array}{lcl}
\delta(q_0,x,z) & = & \{(q_0,xz)\} \\
\...
...a(q,x,z) & = & \{\} \qquad \textrm{everywhere else}
\end{array}\end{displaymath}

where $ q\in Q,x\in\Sigma,z\in\Gamma$. We obtain the previous table by expanding all the possibilities for $ q,x,z$.


next up previous
Next: How does a PDA Up: Pushdown automata Previous: Pushdown automata
Thorsten Altenkirch 2001-05-08