Library

DFA · Regular

As many ab’s as ba’s

Counting two kinds of substring sounds like it needs a counter. It does not: every switch from a to b is followed by a switch back or by the end, so the counts are equal exactly when the word starts and ends with the same letter.

starta..ab..ba..bb..aababbabaab
The machine as drawn — 5 states, 10 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → acceptaabba → accepta → acceptaaaaaaabba → acceptbabba → rejectba → rejectbaaaaaabba → rejectab → reject