Drawtomata / Regular expression to DFA converter

Regular expression to DFA converter

Type a regular expression such as (a+b)*abb above. Drawtomata builds the λ-NFA by Thompson’s construction, removes λ-moves, converts to a DFA by subset construction and minimizes it, showing the table for each step.

The steps

  1. RE → λ-NFA (Thompson): one small NFA per symbol, joined with λ-moves for union (+), concatenation and star (*).
  2. λ-NFA → NFA: compute the λ-closure of every state and rebuild the moves without λ.
  3. NFA → DFA: subset construction, where each DFA state is a set of NFA states.
  4. DFA → minimal DFA: merge states that no string can tell apart, by the table-filling (mark) method or π-partitions.

Each stage is checked against the others, so the final DFA is guaranteed to accept exactly the language of the expression.

Syntax

Use + for union, * for Kleene star, juxtaposition for concatenation and parentheses for grouping. Write the empty string as λ, ε or @, and the empty set as ∅. For example (0+1)*01, a(a+b)*b and (ab+ba)*.

Questions

Why do different books get different NFAs for the same expression?

Thompson’s construction adds λ-moves in a fixed pattern; some books shortcut it. The NFAs differ, but the minimal DFA is the same for every correct method, up to the names of the states.

Can I go back from a DFA to a regular expression?

Yes, with state elimination.