Library

DPDA · Deterministic context-free

More a’s than b’s: aⁿbᵐ, n > m

Push the a’s, pop one per b, and accept while an A is still left. A deterministic machine cannot look at its stack and keep reading in the same breath, so after each pop it steps aside to check the top and moves to “ahead” or “even” — the accepting state is a fact about the stack, carried in the control.

startascheckaheadeven
The machine as drawn — 5 states, 6 transitions.

The author’s examples, run

a → acceptaab → acceptaaabb → acceptaaaaaaaabbbbb → acceptb → rejectbab → rejectbaabb → rejectbaaaaaaabbbbb → reject