Library

DFA · Regular

a’s a multiple of 3, b’s even

Two independent counters — a’s mod 3 and b’s mod 2 — run side by side. The machine is their product: six states laid out as a 3 × 2 grid, where a moves along a row and b moves between them.

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

The author’s examples, run

ε → acceptaabba → acceptbb → acceptaaaaababbb → accepta → rejectbabba → rejectab → rejectbaaaababbb → reject