Library

DFA · Regular

Sipser’s M2: ends in 1

Two states that record only the last symbol read; the accepting one is “the last symbol was a 1”. The smallest machine whose state means something.

q1q20110
The machine as drawn — 2 states, 4 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

1 → accept10011 → accept01 → accept0000001011 → accept0 → reject10010 → reject00 → reject0000001010 → reject