Library

DFA · Regular

An even number of 0s and an even number of 1s

Four states, one for each pair of parities, drawn as a square: a 0 moves across it, a 1 moves up or down. The accepting corner is where both parities are even.

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

The author’s examples, run

ε → accept0011 → accept000101 → accept0000000110 → accept0 → reject1011 → reject100101 → reject1000000110 → reject