Library

NFA · Regular

The third symbol from the end is a 1, by guessing

Four states: wait, then guess that this 1 is the third from the end and check that exactly two symbols follow. The DFA for the same language needs eight — the guess replaces remembering the last three symbols.

q0q1q2q30, 110, 10, 1
The machine as drawn — 4 states, 7 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

100 → accept0110 → accept00100 → accept0000000110 → accept000 → reject0010 → reject00000 → reject0000000010 → reject