Library

DFA · Regular

Decimal multiples of 3: the digit-sum rule

A number is divisible by 3 exactly when its digit sum is, so three states — the digit sum mod 3 — are enough for numbers of any length. Every digit is one of three edges: 0, 3, 6, 9 change nothing.

r0r1r20, 3, 6, 91, 4, 72, 5, 80, 3, 6, 91, 4, 72, 5, 80, 3, 6, 91, 4, 72, 5, 8
The machine as drawn — 3 states, 30 transitions.

The author’s examples, run

3 → accept491568237 → accept52755102 → accept190851702 → accept1 → reject291568237 → reject12755102 → reject290851702 → reject