Library

DFA · Regular

Sipser’s M5: a running sum mod 3, with reset

The symbols are 0, 1, 2 and R (Sipser’s ⟨RESET⟩). The machine keeps the sum of the numbers since the last reset, mod 3, and accepts when it is 0. A reset is one more edge out of every state, all landing at the start.

q0q1q20, R12012, R01, R2
The machine as drawn — 3 states, 12 transitions.Every word up to length 4, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → accept012R → accept0020R10221 → accept01R00RR0211221 → accept1 → reject0121 → reject0020010221 → reject01R00R10211221 → reject