Library

DFA · Regular

Decimal multiples of 5: only the last digit counts

A remainder machine for 5 would need five states, but this one needs two. 10 is a multiple of 5, so every digit before the last contributes nothing to the remainder, and the machine only has to ask whether the last digit was 0 or 5.

noyes0, 51, 2, 3, 4, 6…0, 51, 2, 3, 4, 6…
The machine as drawn — 2 states, 20 transitions.

The author’s examples, run

5 → accept84679320 → accept507801775 → accept21945730 → accept1 → reject84679321 → reject507801771 → reject21945731 → reject