Library

Counter · One-counter

As many a’s as b’s, with one counter

A counter holds a single number, so it cannot store which letter is ahead — but the control can. The states remember the sign of #a − #b and the counter its size; reaching zero sends the machine back to the accepting state. The same language as the stack machine for it, with half the memory.

evenaAheadbAheadaCheckbCheck
The machine as drawn — 5 states, 10 transitions.

The author’s examples, run

ε → acceptaabb → acceptba → acceptbaabbaabbaab → accepta → rejectbabb → rejectaa → rejectaaabbaabbaab → reject