Why this project?
Every developer uses regular expressions, but most have never seen what actually happens when a regex engine processes a pattern. The regex engine doesn't just scan text — it builds a finite state machine (DFA) from your pattern, then walks that machine character by character. Regex Graph makes this invisible machinery visible and interactive.
What is it?
An interactive visualizer that takes a regular expression, compiles it into a Deterministic Finite Automaton (DFA) using Thompson's construction and subset construction, and renders the resulting state machine as a fully interactive diagram. You can trace any string through the machine step-by-step to see how the DFA decides whether the input matches.
How does it work?
Regex Parsing: The input regex is parsed into an abstract syntax tree (AST) supporting literals, concatenation, alternation (|), Kleene star (*), plus (+), optional (?), character classes ([abc]), and ranges ([a-z]).
Thompson's Construction: The AST is converted to an NFA (nondeterministic finite automaton) using Thompson's algorithm. Each operator produces a small NFA fragment that's composed together.
Subset Construction: The NFA is determinized into a DFA using the powerset/subset construction algorithm. Each DFA state represents a set of possible NFA states.
Visualization: The DFA is laid out using a force-directed graph algorithm on an HTML Canvas, with accepting states shown as double circles and transitions as labeled arrows.
Tracing: When you enter a string, the DFA is stepped through character-by-character, highlighting the current state and transition.