Library

NFA · Regular

Two a’s exactly three apart

Somewhere in the word, an a followed by any two symbols and then another a. The NFA waits, guesses the first a, and counts three; a DFA would have to remember the positions of the a’s among the last three symbols.

waitd0d1d2founda, baa, ba, baa, b
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

aaaa → acceptaabba → acceptaaaaaa → acceptaaaaaaabba → acceptbaaa → rejectabbba → rejectε → rejectbaabb → reject