Library

Counter · One-counter

aⁿbᵐ with n ≠ m

Count the a’s up, the b’s down, and accept if the count does not end at zero — either b’s are left over, which the machine notices when it runs out, or a’s are, which it notices at the end. The complement of aⁿbⁿ within a*b*, with the same single counter.

asbsmore_amore_b
The machine as drawn — 4 states, 8 transitions.

The author’s examples, run

a → acceptaab → acceptbb → acceptaaabbbbbbbbbbb → acceptε → rejectbab → rejectab → rejectbaabbbbbbbbbbb → reject