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
is deterministic (is a DPDA) iff
That is: a DPDA may get stuck but it has never any choice.
In our example the automaton is not deterministic, e.g. we have
and
and hence
.
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 !
Nondeterministic PDAs are more powerful than deterministic
PDAs.
However, we can define a similar language over
which can be recognized
by a deterministic PDA:
We define a DPDA for
:
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.