Library

NFA · Regular

(ab ∪ aba)*

Three states, and one choice: after ab, is that the end of a block, or will an a finish an aba? The NFA keeps both possibilities alive. The textbook example where an NFA is easier to draw than to determinise.

q0q1q2abba
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

ε → acceptaba → acceptabaab → acceptabaabaabab → accepta → rejectbba → rejectbbaab → rejectbbaabaabab → reject