What is a pushdown automaton?

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

• A finite set $Q$ of states,

• A finite set $\Sigma$ of symbols (the alphabet),

• A finite set $\Gamma$ of stack symbols,

• A transition function
  $$\delta\in Q\times(\Sigma\cup\{\epsilon\})\times \Gamma \to {\cal P}_{\textrm{fin}}(Q\times\Sigma^*)$$
  Here ${\cal P}_{\textrm{fin}}(A)$ are the finite subsets of a set, i.e. this can be defined as
  $${\cal P}_{\textrm{fin}}(A) = \{ X \mid X \subseteq A \wedge X \textrm{is finite.} \}$$

• An initial state $q_0 \in Q$,

• An initial stack symbol $Z_0 \in \Gamma$,

• A set of final states $F\subseteq Q$.

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.

$${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{array}{lcl} \delta(q_0,0,\char93 ) & = & \{(q_0,0\cha... ...a(q,w,z) & = & \{\} \qquad \textrm{everywhere else} \end{array}$$

To save space we may abbreviate this by writing:

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

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