An interactive finite automaton simulator built with Next.js and TypeScript. Convert regular expressions into NFAs via Thompson's construction, transform them into DFAs using subset construction, visualize state diagrams, and simulate string acceptance — all in the browser.

Live Demo: https://fa.rakeshan.me/

• Regex → NFA — Converts regular expressions to non-deterministic finite automata using Thompson's construction
• NFA → DFA — Optional conversion to a deterministic finite automaton via subset construction
• DFA Minimization — Reduces DFA states using partition refinement (Hopcroft's algorithm)
• State Diagram Visualization — Interactive graph rendering of NFA/DFA state diagrams
• String Simulation — Step-by-step simulation of input strings to check acceptance
• Regex Validation — Input validation and tokenization of regular expressions

# Clone the repository
git clone https://github.com/KRakeesh04/FA-simulator.git
cd FA-simulator

# Install dependencies
bun install

# Start the development server
bun dev

Open http://localhost:3000 in your browser.

1. Enter a regular expression (e.g. (a|b)*abb) in the input field.
2. Click Build NFA to generate the non-deterministic finite automaton.
3. Optionally convert to a DFA or minimize the DFA using the control buttons.
4. View the resulting state diagram in the visualization panel.
5. Enter a test string and run the simulation to check whether it is accepted or rejected.

src/
├── app/
│   ├── globals.css          # Global styles
│   ├── layout.tsx           # Root layout
│   └── page.tsx             # Main page
├── components/
│   ├── Controls.tsx         # Build / convert / minimize buttons
│   ├── DiagramView.tsx      # State diagram visualization
│   ├── RegexInput.tsx       # Regex input field with validation
│   └── SimulationPanel.tsx  # String simulation interface
├── core/
│   ├── graphAdapter.ts      # Converts automata to graph data
│   ├── minimizeDFA.ts       # DFA minimization (Hopcroft's)
│   ├── postfix.ts           # Infix-to-postfix regex conversion
│   ├── simulator.ts         # NFA / DFA string simulation
│   ├── subsetConstruction.ts # NFA → DFA subset construction
│   ├── thompson.ts          # Thompson's construction (regex → NFA)
│   └── tokenizer.ts         # Regex tokenizer
├── types/
│   └── automata.ts          # Type definitions for states & transitions
└── utils/
    └── validation.ts        # Regex input validation helpers

Converts a regular expression into an equivalent ε-NFA by recursively building small automata for each operator (concatenation, union, Kleene star) and composing them.

Transforms an NFA into a DFA by computing the ε-closure of state sets and mapping each unique set to a single DFA state.

Reduces the number of DFA states by iteratively partitioning states into equivalence classes based on transition behavior, producing the minimal equivalent DFA.

Converts an infix regular expression with explicit concatenation operators into postfix notation, enabling straightforward recursive construction of the NFA.

• a
• ab
• a|b
• a*
• (ab)*
• a+
• (ab)+
• a?
• (a|b)*
• (a|b)*abb
• a(b|c)d
• (a|b)(c|d)
• ((a|b)*c)*
• (a|b)*a(a|b)*
• (a|b|c)*

• Animated step-by-step NFA/DFA simulation with state highlighting
• Export state diagrams as SVG / PNG
• Support for extended regex operators (+, ?, character classes)
• Shareable URLs encoding the automaton state
• Dark / light theme toggle
• Mobile-responsive layout
• Unit tests for core algorithms

This project is licensed under the MIT License.