Library

NFA · Regular

Some letter occurs twice

Guess the letter and the moment of its first occurrence, then wait for the second. Every word of length four or more over a, b, c is accepted — the pigeonhole principle, visible as a machine.

startseenAseenBseenCtwicea, b, cabca, b, caa, b, cba, b, cca, b, c
The machine as drawn — 5 states, 21 transitions.Every word up to length 5, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

aa → acceptabacbbc → acceptcca → acceptabbcaababcaccb → acceptba → rejectbca → rejectε → rejectabc → reject