Library

DFA · Regular

Starts with 0 and has odd length, or starts with 1 and even length

Two conditions that look like two branches, each with its own parity counter. Minimise it and the branches collapse into one: after the first symbol, all that matters is whether the length so far has the parity that symbol asked for. Three states.

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

The author’s examples, run

0 → accept00110 → accept10 → accept1000000011 → accept1 → reject10110 → reject00 → reject0000000011 → reject