Library

NFA · Regular

Contains a square of length 4

Accept any word containing xx where x is two letters — abab, aaaa, baba, bbbb. The machine guesses where the square starts, remembers the two letters of x, and checks that they come again.

startabaaabbabbaa_aab_aba_bbb_bfounda, babababaabbababa, b
The machine as drawn — 12 states, 18 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 → acceptababb → acceptaaaaaa → acceptaaaaaaabba → acceptbaaa → rejectbbabb → rejectaabaaa → rejectaaabaaabba → reject