Library

ε-NFA · Regular

Sipser’s N3: unary lengths divisible by 2 or 3

An ε-move from the start chooses between a cycle of two and a cycle of three, each accepting at its own beginning. The DFA for the same language is one cycle of six — the product of the two.

starttwo0three0two1three1three2εε00000
The machine as drawn — 6 states, 7 transitions.Every word up to length 14, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

ε → accept00 → accept000 → accept00000000000000 → accept0 → reject0000000000000 → reject00000 → reject0000000 → reject