Library

NFA · Regular

Lengths that are multiples of 3 or of 5

Two cycles, three and five long, and a first step that chooses between them: nine states. A DFA cannot choose, so it runs both at once on a single cycle of lcm(3, 5) = 15. For unary languages that gap can be made exponential.

startt1f1t2t0f2f3f4f0aaaaaaaaaa
The machine as drawn — 9 states, 10 transitions.Every word up to length 14, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → acceptaaa → acceptaaaaa → acceptaaaaaaaaaaaa → accepta → rejectaa → rejectaaaa → rejectaaaaaaaaaaa → reject