How does a PDA work?

At any time the state of a PDA $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ is given by:

• the state $q\in Q$ the PDA is in,

• the input string $w\in\Sigma^*$ which still has to be processed,

• the contents of the stack $\gamma \in \Gamma^*$.

Such a triple $(q,w,\gamma)\in Q\times \Sigma^*\times \Gamma^*$ is called an instantanous description ( $\textrm{ID})$.

We define a relation $\vdash_P\subseteq \textrm{ID}\times\textrm{ID}$ between IDs which describes how the PDA can change from one ID to the next one. Since PDAs in general are nondeterministic this is a relation (not a function), i.e. there may be more than one possibility.

There are two possibilities for $\vdash_P$:

1. $(q,xw,z\gamma) \vdash_P (q',w,\alpha\gamma)$ if $(q',\alpha)\in \delta(q,x,z)$

2. $(q,w,z\gamma) \vdash_P (q',w,\alpha\gamma)$ if $(q',\alpha)\in \delta(q,\epsilon,z)$

In the first case the PDA reads an input symbol and consults the transition function $\delta$ to calculate a possible new state $q'$ and a sequence of stack symbols $\alpha$ which replace the currend symbol on the top $z$.

In the second case the PDA ignores the input and silently moves into a new state and modifies the stack as above. The input is unchanged.

Consider the word $0110$ -- what are possible sequences of IDs for ${P_0}$ starting with $(q_0,0110,\char93 )$ ?

$$\begin{array}{ll@{\hspace{3ex}}l} (q_0,0110,\char93 ) & \vdas... ...$(q_2,\epsilon)\in\delta(q_1,\epsilon,\char93 )$} \end{array}$$

We write $(q,w,\gamma)\vdash_P^*(q',w',\gamma)$ if the PDA can move from $(q,w,\gamma)$ to $(q',w',\gamma')$ in a (possibly empty) sequence of moves. Above we have shown that $(q_0,0110,\char93 )\vdash_{P_0}^*(q_2,\epsilon,\epsilon)$.

However, this is not the only possible sequence of IDs for this input. E.g. the PDA may just guess the middle wrong:

$$\begin{array}{ll@{\hspace{3ex}}l} (q_0,0110,\char93 ) & \vdas... ...extrm{2. with $(q_1,0)\in\delta(q_0,\epsilon,0)$} \end{array}$$

We have shown $(q_0,0110,\char93 )\vdash_{P_0}^* (q_1,110,0\char93 )$. Here the PDA gets stuck there is no state after $(q_1,110,0\char93 )$.

If we start with a word which is not in the language $L$ (like $0011$) then the automaton will always get stuck before reaching a final state.