1. δ(q, a, b) contains at most one element,
2. if δ (q, λ, b) is not empty, then δ (q, c, b) must be empty for every c ∈ Σ.
The first of these conditions simply requires that for any given input symbol and
any stack top, at most one move can be made. The second condition is that when
a λ-move is possible for some configuration, no input-consuming alternative is
available.
It is interesting to note the difference between this definition and the
corresponding definition of a deterministic finite automaton. The domain of the
transition function is still as in Definition 7.1 rather than Q × Σ × Γ because we
want to retain λ-transitions. Since the top of the stack plays a role in determining
the next move, the presence of λ-transitions does not automatically imply
nondeterminism. Also, some transitions of a dpda may be to the empty set, that
is, undefined, so there may be dead configurations. This does not affect the
definition; the only criterion for determinism is that at all times at most one
possible move exists.
Definition 7.4
A language L is said to be a deterministic context-free language if and only if
there exists a dpda M such that L = L (M).
Example 7.10
The language
L = {a n b n : n ≥ 0}
is a deterministic context-free language. The pda M =({q 0 , q 1 , q 2 }, {a,b}, {0,1},
δ, q 0 , 0, {q 0 })with