Library

DFA · Regular

A byte with even parity

Eight data bits and a parity bit, nine in all, with an even number of 1s. The states are a grid: how many bits have been read, and the parity so far. Fixed length and counting, in one picture.

0even1even1odd2even2odd3even3odd4even4odd5even5odd6even6odd7even7odd8even8odd9even
The machine as drawn — 18 states, 32 transitions.

The author’s examples, run

000000000 → accept000000110 → accept000001100 → accept000000011 → accept100000000 → reject100000110 → reject100001100 → reject100000011 → reject