Library

DFA · Regular

No two 0s in a row

Two states: the last symbol was a 1 (or nothing yet), or it was a 0. The number of such words of length n is a Fibonacci number — the states are the two terms of the recurrence.

last1last0101
The machine as drawn — 2 states, 3 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → accept0110 → accept0 → accept0101010110 → accept0010 → reject00 → reject0001010110 → reject00110 → reject