accepts the given language. It satisfies the conditions of Definition 7.3 and is
therefore deterministic.
Look now at Example 7.5. The npda there is not deterministic because
and
and
violate condition 2 of Definition 7.3. This, of course, does not imply that the
language {ww R } itself is nondeterministic, since there is the possibility of an
equivalent dpda. But it is known that the language is indeed not deterministic.
From this and the next example we see that, in contrast to finite automata,
deterministic and nondeterministic pushdown automata are not equivalent. There
are context-free languages that are not deterministic.
Example 7.11
Let
L 1 = {a n b n : n ≥ 0}
and
L 2 = {a n b 2n : n ≥ 0}.
An obvious modification of the argument that L 1 is a context-free language
shows that L 2 is also context-free. The language