Library

DFA · Regular

Sipser’s M1: a 1, then an even number of 0s

The first finite automaton in Sipser’s book. It accepts a string when it contains at least one 1 and an even number of 0s follow the last 1. Three states: no 1 yet, an even run of 0s since the last 1, and an odd one.

q1q2q301100, 1
The machine as drawn — 3 states, 6 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 → accept01100 → accept01 → accept0000001011 → accept0 → reject01000 → reject00 → reject0000001010 → reject