Regex2DFA

A small utility that converts a regular expression into a minimal DFA (that is equivalent to the regex) and emits a Graphviz DOT file.

What it does

Given a regular expression over the alphabet {a,b,...,z} (supports |, *, (, )), the program:

• builds an NFA (Thompson construction),
• removes epsilon-transitions and determinizes to a DFA,
• minimizes the DFA,
• writes the minimized automaton to min_dfa.dot (Graphviz DOT).

Example

Regex:

a(a|b)*a | a(a|b)*b | b(a|b)*a | b(a|b)*b

Min-DFA:

This example describes any strings over {a,b} of length at least 2.