Library

DFA · Regular

Contains 001

Sipser’s worked example of designing a DFA by asking what to remember: nothing useful yet, a 0, 00, or the whole pattern. After 00 a further 0 changes nothing — the last two symbols are still 00.

qq0q00q0011010010, 1
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

001 → accept00110 → accept0001 → accept0000000110 → accept101 → reject10110 → reject0101 → rejectε → reject