Library

ε-NFA · Regular

Thompson’s construction of (a|b)*abb

The ε-NFA that Thompson’s construction builds from the regular expression (a|b)*abb, state for state as in the dragon book: each operator contributes a small gadget, and ε-moves glue the gadgets together.

017243568910εεεεabεεεεabb
The machine as drawn — 11 states, 13 transitions.Every word up to length 8, one row per length in shortlex order, inked where it is accepted.

The author’s examples, run

abb → acceptbaabb → acceptaabb → acceptaaaaaababb → acceptbbb → rejectbabbb → rejectabbb → rejectaaaaaabbbb → reject