Library

DFA · Regular

Binary numbers greater than 5

Once the value read so far is at least 3, any further bit pushes it past 5 for good, so 3, 4 and 5 are one state. A threshold needs a state for each value below it that can still behave differently — here 0, 1, 2 and "at least 3".

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

The author’s examples, run

110 → accept1001 → accept10000 → accept1000000011 → accept100 → reject101 → reject1 → reject11 → reject