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
- RE → λ-NFA (Thompson): one small NFA per symbol, joined with λ-moves for union (+), concatenation and star (*).
- λ-NFA → NFA: compute the λ-closure of every state and rebuild the moves without λ.
- NFA → DFA: subset construction, where each DFA state is a set of NFA states.
- 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.