Library

DFA · Regular

Binary multiples of 6, in four states

A remainder machine for 6 would have six states, but two pairs of them can be merged: from remainder 1 and from remainder 4 the same continuations reach 0, because 2·1 and 2·4 are both 2 mod 6. Divisibility by 6 is divisibility by 2 and by 3, and the last bit already says the first.

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

The author’s examples, run

110 → accept10010 → accept1100 → accept1000010110 → accept100 → reject11010 → reject1000 → reject1100010110 → reject