Library

ε-NFA · Regular

Sipser’s N1: contains 101 or 11

The NFA Sipser uses to introduce nondeterminism. In q1 it may stay or guess that this 1 starts the pattern; from q2 the ε-move lets the middle 0 be skipped, so the same three edges match both 101 and 11.

q1q2q3q40, 110, ε10, 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

11 → accept101 → accept0011 → accept0000000110 → accept01 → reject001 → reject0001 → reject0000000010 → reject