◉━━◉

AUTOMATA VISUALIZER

REGEX → ε-NFA → NFA → DFA → MIN. DFA

▸ REGEX INPUT

EXPRESSION

▸ TEST STRING

INPUT STRING

▸ EXPORT

▸ STATISTICS

STATES —

TRANS —

ALPHA —

FINAL —

┌── AUTOMATON VISUALIZATION ──┐

ENTER REGULAR EXPRESSION

PRESS FOR PATTERNS

▸ BATCH TESTING

MULTIPLE INPUT STRINGS (ONE PER LINE)

REGULAR EXPRESSION SYNTAX

OPERATOR	DESCRIPTION	EXAMPLE
`a`	Literal character	`a` matches "a"
`\|`	Alternation (OR)	`a\|b` matches "a" or "b"
`*`	Kleene star (0 or more)	`a*` matches "", "a", "aa", ...
`+`	Plus (1 or more)	`a+` matches "a", "aa", ...
`?`	Optional (0 or 1)	`a?` matches "" or "a"
`()`	Grouping	`(ab)*` matches "", "ab", "abab", ...
`ε`	Epsilon (empty string)	`ε` matches empty string

KEYBOARD SHORTCUTS

Ctrl + Enter → Visualize regex
Ctrl + T → Test string
Ctrl + E → Export SVG
+ / - → Zoom in/out
R → Reset view
? → Show help

CONVERSION PROCESS

REGEX: Input regular expression
ε-NFA: Convert to epsilon-NFA using Thompson's construction
NFA: Remove epsilon transitions
DFA: Convert to DFA using subset construction

USAGE TIPS

Click on stage buttons to view different conversion steps
Hover over states to see their details
Use the batch testing feature to test multiple strings at once
Export visualizations for use in presentations or reports

CONVERSION PIPELINE

This application converts your regular expression into a Deterministic Finite Automaton (DFA) through a multi-stage process. Here's how it works behind the scenes:

Regex Parsing: Your regular expression is parsed into an Abstract Syntax Tree (AST). The parser recognizes operators like | (union), * (Kleene star), + (one or more), ? (optional), and () (grouping).
Thompson's Construction (ε-NFA): The AST is converted into an Epsilon Non-deterministic Finite Automaton (ε-NFA) using Thompson's algorithm. Each regex operator is translated into a small NFA fragment with epsilon (ε) transitions that allow state changes without consuming input.
Epsilon Removal (NFA): All epsilon transitions are eliminated by computing epsilon closures. For each state, we find all states reachable via epsilon transitions and create direct transitions on actual symbols. This produces a standard NFA without epsilon transitions.
Subset Construction (DFA): The NFA is converted to a DFA using the powerset construction algorithm. Each DFA state represents a set of NFA states. We systematically explore all possible symbol transitions from each set of states, creating new DFA states as needed. This ensures determinism—each state has exactly one transition per symbol.
State Naming: DFA states are assigned readable labels (q0, q1, q2, etc.) instead of showing the internal set representation. Dead states (trap states with no accepting paths) are labeled with Φ (phi symbol).
Visualization: The final DFA is rendered as an interactive graph using D3.js force simulation. Start states are highlighted in amber, accepting states in green, and transitions are labeled with their input symbols. You can zoom, pan, and drag nodes to explore the automaton.

TESTING MECHANISM

When you test a string against the DFA:

Initialization: The simulator starts at the DFA's start state.
Symbol Processing: For each character in your input string, the simulator looks up the transition from the current state on that symbol and moves to the next state.
Acceptance Check: After processing all characters, if the final state is an accepting state, the string is ACCEPTED. Otherwise, it's REJECTED. If no valid transition exists for a symbol, the string is immediately rejected.

TECHNICAL DETAILS

COMPONENT	TECHNOLOGY	PURPOSE
Parser	Recursive Descent	Converts regex string to AST
ε-NFA Builder	Thompson's Algorithm	AST to epsilon-NFA conversion
NFA Converter	Epsilon Closure	Removes epsilon transitions
DFA Builder	Subset Construction	NFA to DFA determinization
Visualization	D3.js Force Graph	Interactive automaton rendering
Simulator	State Machine	String acceptance testing

ALGORITHMS USED

Thompson's Construction: Compositional NFA building from regex operators
Epsilon Closure: BFS/DFS to find ε-reachable states
Powerset Construction: Systematic exploration of NFA state combinations
Force-Directed Layout: Physics simulation for graph positioning

┌── AUTOMATON VISUALIZATION ──┐

◆ TRANSITION TABLE

◆ STATE INFORMATION

◆ CONVERSION LOG

▸ BATCH TESTING