Library

DFA · Regular

An even number of inversions

An inversion is a 1 somewhere before a 0. Counting them all looks quadratic, but only the parity is asked for: each 0 adds the number of 1s before it, so the parity of the 1s is all the machine needs alongside its answer.

even1s·e…odd1s·ev…odd1s·od…even1s·o…01010101
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

ε → accept00110 → accept0 → accept0000000110 → accept01110 → reject10 → reject1000000110 → reject001011 → reject