Library

DFA · Regular

Comparing two binary numbers, column by column

Each symbol is a column: the top number’s bit, then the bottom one’s. Reading from the most significant end, the first column that differs decides — after that nothing can change the answer.

samebiggersmaller00, 11100100, 01, 10, 1100, 01, 10, 11
The machine as drawn — 3 states, 12 transitions.Every word up to length 4, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

10 → accept00 10 01 11 → accept00 00 11 10 10 11 01 01 → accept00 10 10 01 01 10 10 00 10 11 11 00 01 00 → accept00 → reject01 10 01 11 → reject01 00 11 10 10 11 01 01 → reject01 10 10 01 01 10 10 00 10 11 11 00 01 00 → reject