the DPDA is strictly weaker than the PDA

Here is the single most surprising fact about pushdown automata, and it is worth stating bluntly: adding determinism to a PDA REMOVES power. The deterministic PDA recognises strictly fewer languages than the general nondeterministic PDA. This flatly contradicts the intuition built from finite automata, where determinism is free and every NFA has an equivalent DFA. For pushdown machines, the stack changes everything.

The proof that the inclusion is strict comes from exhibiting a witness: a language that a nondeterministic PDA recognises but no deterministic PDA can. The classic witness is the set of even-length palindromes ww^R over {a, b}. A nondeterministic PDA recognises it by pushing the first half and guessing where the middle is, then popping to match the second half. But a deterministic PDA, having only one move at each step, cannot guess the midpoint — and one can prove rigorously that no DPDA recognises this language. Since the language IS context-free (a simple grammar generates it) yet is not deterministic context-free, the deterministic class is a proper subset.

This asymmetry is the reason determinism matters so much in practice. Because a deterministic PDA runs without backtracking and in linear time, compiler writers deliberately design programming-language grammars to stay within the deterministic context-free languages (LL and LR grammars). When a grammar accidentally needs nondeterministic power, parser generators report conflicts — shift-reduce or reduce-reduce — which is exactly the tooling refusing to build a deterministic machine for an inherently nondeterministic specification. The lesson generalises: nondeterminism is harmless for finite automata but genuinely powerful for pushdown automata.