ToolSphere

Regex to NFA Converter

Computer science

Convert a regular expression to an ε-NFA by Thompson's construction and see the diagram. Supports |, *, +, ?, ε and brackets. Free, no sign-up.

Regex to NFA converter

Type a regular expression and its ε-NFA (Thompson's construction) appears as you type. Supports | * + ? ( ), ε, character classes like [A-Za-z0-9] and [^0-9], . (any character), \d \w \s, and counts like {2} or {2,4}.

Try:

Thompson NFA: 11 states, 13 transitions

abεεεεεεεεabbq0q1q2q3q4q5q6q7q8q9q10
Accepted

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

Coming from JFLAP? See what carries over and what JFLAP still does better →

How to use Regex to NFA Converter

  1. 1Type a regular expression; the ε-NFA appears as you type. Use | * + ? and brackets, ε for the empty string, character classes such as [A-Za-z0-9] or [^0-9], . for any character, \d \w \s, and counts like {2,4}.
  2. 2Tick Textbook notation if your course writes union as + (so a+b means a or b).
  3. 3Read the Thompson NFA: one start state, one accepting state, and ε-moves joining the pieces. A class like [A-Za-z] is one edge, not one state per letter.
  4. 4Type a word into Test a string to see whether the expression accepts it.
  5. 5Continue to the NFA to DFA converter or trace strings step by step in the simulator.

About Regex to NFA Converter

Regular expression to NFA, the textbook way

Every regular expression has an equivalent NFA, and Thompson's construction builds it mechanically from the expression's structure. The converter parses your expression (respecting precedence: * binds tightest, then concatenation, then |), then combines small NFAs bottom-up:

  • A symbol a becomes two states joined by an a-transition.
  • Union r|s adds a new start state with ε-moves into both machines, and ε-moves from both accepting states into a new accepting state.
  • Concatenation rs joins the accepting state of r to the start of s.
  • Kleene star r* adds a new start and accepting state, an ε-move that skips r entirely (zero repetitions) and an ε-move from r's end back to its start (more repetitions).

The result always has exactly one start state and one accepting state, and at most two transitions leaving any state, which is what makes Thompson NFAs easy to simulate.

Worked example: (a|b)*abb

The default expression is the classic from the "Dragon Book" (Aho, Lam, Sethi and Ullman): all strings over {a, b} ending in abb.

  1. a and b each become a two-state NFA (4 states).
  2. a|b wraps them with a new start and accepting state: 6 states.
  3. (a|b)* wraps that again for the star: 8 states.
  4. Concatenating a, b and b adds one new state each: 11 states in total, the same count as the Dragon Book's figure.

Trace babb through it and the ε-closures behave exactly like the hand-built four-state NFA for "ends in abb" in the NFA & DFA simulator: Thompson's version is bigger because every operator adds its own ε-glue, but it accepts the same language.

Syntax the converter accepts

Write Meaning
a, 0, x one input symbol (any single character except the operators)
rs r followed by s (no operator needed)
r|s r or s
r* zero or more r
r+ one or more r
r? r or nothing
ε the empty string
( … ) grouping

+ and ? get their own Thompson pictures: r+ is the star construction without the ε-move that skips r, and r? is the star construction without the ε-move that loops back. Spaces are ignored, and a malformed expression (an unclosed bracket, an empty side of |) is pointed out with its position.

From regex to minimal DFA

This is the first step of the standard pipeline in compiler design and theory-of-computation courses: regex → NFA (here) → DFA by the subset construction → smallest DFA with the DFA minimizer. For (a|b)*abb that pipeline ends in the well-known four-state DFA. Lexer generators such as lex and flex follow the same route to turn token patterns into fast scanners; the regular expressions guide covers the practical side.

Guides and tutorials

Frequently asked questions

How do I convert a regular expression to an NFA?

Use Thompson's construction: build a two-state NFA for each symbol, then combine them following the expression's structure, adding ε-moves for union and Kleene star and joining machines end to start for concatenation. Type the expression here and the converter does each step and draws the result.

Why does the NFA have so many ε-transitions?

Every union and star in Thompson's construction adds new states joined by ε-moves. They keep each piece independent, which makes the construction mechanical and the NFA easy to simulate, at the cost of extra states. Converting to a DFA and minimizing removes them.

How many states does the Thompson NFA have?

At most twice the number of symbols and operators in the expression. Each symbol contributes two states and each union or star two more; in this converter each concatenation merges two states into one. (a|b)*abb gives 11 states.

Does it support + and ?

Yes. r+ (one or more) is built like r* but without the ε-move that skips r, and r? (optional) like r* but without the ε-move back to the start. Both are shorthand: r+ means rr* and r? means (r|ε), and the NFA accepts exactly the same strings.

What precedence do the operators have?

Kleene star binds tightest, then concatenation, then union. So ab*|c means (a(b*))|c. Use brackets whenever you mean something else, such as (ab)* or a(b|c).

How do I get a DFA from the regular expression?

Convert the expression to an NFA here, then apply the subset construction in the NFA to DFA converter. Finish with the DFA minimizer to get the smallest DFA for the language.

Is Thompson's construction the only method?

No. The Glushkov (position) construction gives an ε-free NFA with one state per symbol plus a start state, and the direct method from the Dragon Book builds a DFA from the syntax tree using followpos. Thompson's is the one most courses teach first because each operator maps to a small fixed picture.

Have a suggestion for Regex to NFA Converter?Share your feedback ↗