Library

DPA · ω-regular

The parity condition itself

Letters 0, 1, 2 and 3 are priorities, and each state remembers the last one read. So the machine accepts exactly when the smallest priority that keeps coming back is even — the parity condition, turned into a language. Every parity game is played over words like these.

p3p0p1p20123012301230123
The machine as drawn — 4 states, 16 transitions.

The author’s examples, run

(0) → accept(2) → accept(00) → accept(01) → accept(1) → reject(3) → reject(11) → reject(12) → reject