Library

DFA · Regular

Even numbers in base 3

In base 10 the last digit says whether a number is even. In base 3 it does not: 3 is odd, so every power of 3 is odd, and a number is even exactly when its digit sum is. Two states count the 1s.

evenodd0, 210, 21
The machine as drawn — 2 states, 6 transitions.Every word up to length 5, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

2 → accept1001121 → accept2022 → accept1000222021112 → accept1 → reject2001121 → reject1022 → reject2000222021112 → reject