About

This tool transforms a Regular Expression into its equivalent Non-Deterministic Finite Automaton (NFA) and Deterministic Finite Automaton (DFA). It is designed for computer science students, compiler engineers, and developers who need to visualize the underlying logic of pattern matching.

Unlike simple simulators, this engine performs a full mathematical conversion. It first parses the regex using the Shunting-Yard algorithm to handle operator precedence. It then applies Thompson's Construction to build the NFA, followed by the Subset Construction method to determinize the graph into a DFA.

Key Features:

Real-time Force-Directed graph visualization.
Support for Union |, Concatenation, Kleene Star *, Plus +, and Optional ? operators.
Interactive canvas: Drag nodes to rearrange the structure.

Formulas

The conversion relies on the formal definition of a Finite Automaton tuple:

M = QΣδq₀F

Where:

Q = Finite set of states.
Σ = Input alphabet (symbols).
δ : Q × Σ → P(Q) is the transition function.
q₀ ∈ Q is the start state.
F ⊂ Q is the set of accept states.

For DFA conversion, we compute the ε-closure for a state s:

closure(s) = { q | s →^ε* q }

Reference Data

Operator / Symbol	Name	Precedence	Description
()	Grouping	1 (Highest)	Defines the scope of operators.
*	Kleene Star	2	Matches 0 or more times.
+	One or More	2	Matches 1 or more times.
?	Zero or One	2	Matches 0 or 1 time.
(implicit)	Concatenation	3	Sequence of characters (e.g., ab).
\|	Union (OR)	4 (Lowest)	Matches either the left or right expression.
ε	Epsilon	N/A	Transition without consuming input.

Frequently Asked Questions

An NFA (Non-Deterministic) allows multiple transitions for the same symbol from a single state, including epsilon (ε) moves. A DFA (Deterministic) has exactly one transition per symbol for every state, making it more efficient for execution but harder to construct directly.

Regexes with nested quantifiers (like (a*)*) or large unions can explode the state space. The DFA conversion process (subset construction) can theoretically result in 2^n states, where n is the number of NFA states.

This tool focuses on "Regular" Regular Expressions (Computer Science theory). It supports basic operators (*, +, ?, |, ()). It does not support PCRE features like lookaheads, lookbehinds, or backreferences, as these require a more complex Pushdown Automaton or Turing Machine logic.

It uses a Force-Directed Graph algorithm (custom implementation). Nodes repel each other like magnets, while transitions act as springs pulling connected nodes together, finding an equilibrium state.