Library

NPDA · Context-free

aⁿbⁿ or aⁿb²ⁿ

Each half is deterministic, but their union is not: having read aⁿbⁿ, a deterministic machine cannot both accept and keep counting for the other n b’s. Nondeterminism postpones the choice — the standard proof that DPDAs are weaker than NPDAs.

startonetwoobdonetb
The machine as drawn — 6 states, 11 transitions.

The author’s examples, run

ε → acceptaabb → acceptab → acceptaaaaaaabbbbbbb → accepta → rejectbabb → rejectbb → rejectbaaaaaabbbbbbb → reject