Library

DFA · Regular

Letters alternate

No aa and no bb: each letter must differ from the one before. Three states — nothing read yet, last was a, last was b.

startlastAlastBabba
The machine as drawn — 3 states, 4 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → acceptaba → accepta → acceptababababab → acceptbba → rejectaa → rejectbbabababab → rejectabba → reject