Regex State Machine Visualizer - Online DFA Diagram

A DFA is a theoretical model of computation consisting of a finite set of states and transitions between them. For each state and input symbol, there is exactly one transition to a next state. DFAs are used to recognize regular languages and are equivalent in power to regular expressions. They are called "deterministic" because the next state is uniquely determined by the current state and input symbol.

The conversion follows three main steps: ① Parse the regex into an abstract syntax tree, ② Build an NFA using Thompson's construction (creating states and epsilon transitions for each regex operator), and ③ Convert NFA to DFA using the subset construction algorithm (each DFA state represents a set of NFA states reachable via epsilon closure). The resulting DFA is then laid out and rendered on the canvas.

Supported operators include: * (Kleene star, zero or more), + (one or more), ? (zero or one), | (alternation/OR), () (grouping), . (any single character), [abc] and [a-z] (character classes), and \ (escape for special characters like \. \* \(). Concatenation is implicit — ab means a followed by b.

Thompson's construction, introduced by Ken Thompson in 1968, is an algorithm for converting a regular expression into an equivalent NFA (Nondeterministic Finite Automaton). It works recursively on the structure of the regex: each basic symbol creates a simple two-state NFA, and operators like union (|), concatenation, and Kleene star (*) combine smaller NFAs into larger ones using epsilon transitions. The resulting NFA has exactly one start state and one accept state.

An NFA (Nondeterministic Finite Automaton) can have multiple possible transitions for the same input symbol from a given state, and can also have epsilon (ε) transitions that don't consume any input. A DFA has exactly one transition per input symbol per state and no epsilon transitions. While NFAs are often more compact, DFAs are more efficient for string matching since there's never any backtracking. Every NFA can be converted to an equivalent DFA, though the DFA may have exponentially more states.

The subset construction algorithm can produce up to 2ⁿ states in the worst case (where n is the number of NFA states). Complex regexes with nested quantifiers, alternations, and character classes can generate larger DFAs. This is inherent to the NFA-to-DFA conversion. For practical regex matching, many engines use lazy DFA construction or hybrid approaches to avoid state explosion.

Circles represent states. The blue arrow pointing into a state marks the start state. Double circles (green outline) are accepting/final states — if the DFA ends in one after processing all input, the string matches. Arrows between states show transitions labeled with the input symbol that triggers them. A loop (arrow curving back to the same state) means that symbol keeps the DFA in that state.