Library

NFA · Regular

Ends in 01, by guessing

The NFA Hopcroft, Motwani and Ullman use to introduce nondeterminism: stay in q0, or guess that this 0 is the second-to-last symbol and check that a 1 and then the end follow. Its DFA has three states too — the guess saves nothing here, which is part of the lesson.

Recognises the same language as Ends in 01, which was listed first.

q0q1q20, 101
The machine as drawn — 3 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

01 → accept11001 → accept001 → accept0000001101 → accept11 → reject11011 → reject011 → reject0000001111 → reject