DPDA · Deterministic context-free
aⁿbⁿ
The language that is not regular: no finite memory can count the a’s, and a stack can. Push one X per a, pop one per b, and accept when the bottom marker comes back into view exactly as the input runs out.
The author’s examples, run
ε → acceptaabb → acceptab → acceptaaaaaaabbbbbbb → accepta → rejectbabb → rejectbb → rejectbaaaaaabbbbbbb → reject