Library

DFA · Regular

Sums of 3s and 5s

Which lengths can be made from steps of 3 and 5? Every one from 8 on, and 0, 3, 5 and 6 below it: 7 is the largest that cannot (the Frobenius number, 3·5 − 3 − 5). A unary machine is a path into a loop, and this one’s loop is a single state.

n0n1n2n3n4n5n6n7n8+aaaaaaaaa
The machine as drawn — 9 states, 9 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 → acceptaaaaaaaaaaaaaa → accepta → rejectaa → rejectaaaa → rejectaaaaaaa → reject