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.
The author’s examples, run
ε → acceptaaa → acceptaaaaa → acceptaaaaaaaaaaaa → accepta → rejectaa → rejectaaaa → rejectaaaaaaaaaaa → reject