Deterministic PDAs

We have introduced PDAs as nondeterministic machines which may have several possibilities how to continue. We now define deterministic pushdown automata (DPDA) as those which never have a choice.

To be precise we say that a PDA $P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$ is deterministic (is a DPDA) iff

$$\vert\delta(q,x,z)\vert+\vert\delta(q,\epsilon,z)\vert \leq 1$$

Remember, that $\vert X\vert$ stands for the number of elements in a finite set $X$.

That is: a DPDA may get stuck but it has never any choice.

In our example the automaton $P_0$ is not deterministic, e.g. we have $\delta(q_0,0,\char93 )=\{(q_0,0\char93 )\}$ and $\delta(q_0,\epsilon,\char93 )=\{(q_1,\char93 )\}$ and hence $\vert\delta(q_0,0,\char93 )\vert+\vert\delta(q_0,\epsilon,\char93 )\vert = 2$.

Unlike the situation for finite automata, there is in general no way to translate a nondeterministic PDA into a deterministic one. Indeed, there is no DPDA which recognizes the language $L$ ! Nondeterministic PDAs are more powerful than deterministic PDAs.

However, we can define a similar language $L'$ over $\Sigma=\{0,1,\$\}$ which can be recognized by a deterministic PDA:

$$L' = \{ w\$w^R \mid w \in \{0,1\}^* \}$$

That is $L'$ contains palindroms with a marker $\$ in the middle, e.g. $01\$10 \in L'$.

We define a DPDA $P_1$ for $L'$:

$${P_1} = (\{ q_0,q_1,q_2 \}, \{0,1,\$\},\{0,1,\char93 \},\delta',q_0,\char93 ,\{q_2\})$$

where $\delta$ is given by:

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

We can check that this automaton is deterministic. In particular the 3rd and 4th line cannot overlap because $\char93$ is not an input symbol.

Different to PDAs in general the two acceptance methods are not equivalent for DPDAs -- acceptance by final state makes it possible to define a bigger class of langauges. hence, we shall always use acceptance by final state for DPDAs.