Library

DFA · Regular

Powers of two in binary

A power of two is a single 1 with zeros around it — leading zeros allowed, any number of zeros after. The third possible state, a second 1, is left out: there is nowhere to go from it.

zerosone010
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

1 → accept100 → accept10 → accept1000000000 → accept11 → reject110 → reject101 → reject1100000000 → reject