Skip to content
Tape‑n‑Trace
PracticeSearch 26 tools

← All conversions

Regular expression → ε-NFA

Thompson's construction, one parse-tree node at a time, bottom-up.

Hopcroft 2e, §3.2.3

Try

Union is + or |; star is *. Write ε for the empty string and ∅ for the empty language. Star binds tightest, then concatenation, then union.

Result · ε-NFA

0 of 12 states

Parse tree

·(0+1)*01·(0+1)*0*(0+1)*+0+100110011

Build an ε-NFA for (0+1)*01 by working up the parse tree, one operator at a time.

The answer appears at the last step. if you would rather read it than watch it.

How to read itHopcroft 2e, §3.2.3
  • The parse tree shows the reading: star binds tightest, then concatenation, then union.
  • Each node builds a fragment with exactly one start and one accepting state, which is what makes the operators composable.
  • The ε-transitions are the price of that composability. Removing them is a separate conversion.