How to use the Regular Expression to NFA (Thompson) Converter
- 1. Type the expressionUse | for union, * for star, ? for optional and ( ) for grouping. Pick what + means in your book.
- 2. Pick a styleMerge states on concatenation (Aho–Ullman) or join the pieces with an ε-move.
- 3. Read the NFASee the construction order, the transition table, ε-closure of the start state and a run on your test string.
Thompson's rules
- Symbol a: new start i, new accept f, move i –a→ f. ε works the same way with an ε-move.
- Union s | t: new start with ε-moves to both starts, and ε-moves from both accepts to a new accept.
- Concatenation st: the accept of N(s) becomes the start of N(t).
- Star s*: new start and accept; ε-moves start → N(s), N(s) accept → N(s) start, N(s) accept → accept and start → accept.
The result has one start state with no incoming moves and one accept state with no outgoing moves, and at most twice as many states as symbols and operators.
Worked example: (a|b)*abb
This is Aho–Ullman's example. The union a | b uses states 1 to 6, the star adds 0 and 7, and abb adds 8, 9 and 10, for 11 states with start 0 and accept 10.
The moves are 0 → 1, 7; 1 → 2, 4; 2 –a→ 3; 4 –b→ 5; 3, 5 → 6; 6 → 1, 7; 7 –a→ 8; 8 –b→ 9; 9 –b→ 10 (unlabelled moves are ε). ε-closure(0) = {0, 1, 2, 4, 7}, which is the start state of the DFA from the subset construction. With the ε-join style, each of the 3 joins adds a state, giving 14.
Frequently asked questions
Does + mean union or one-or-more?
In many theory of computation books a + b means union. In programming, a+ means one or more. Pick the meaning your course uses.
How do I get a DFA from this NFA?
Use subset construction: start from ε-closure of the start state and follow each symbol. Our NFA to DFA converter does this from a transition table.
Why are there so many ε-moves?
Thompson's construction is simple and always correct, but it uses ε-moves to glue pieces together. Subset construction and minimisation remove them later.