Library

DFA · Regular

An even number of 1s

The first DFA in most courses, and the reason it comes first: the machine’s whole memory is one bit — has it seen an even or an odd number of 1s — and the two states are exactly those two answers. A 0 changes nothing.

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

The author’s examples, run

ε → accept00110 → accept0 → accept0000000110 → accept1 → reject10110 → reject10 → reject1000000110 → reject