Regex → Minimized DFA Conversion Simulator

An interactive, high-complexity web application designed for the Theory of Computation course. This project simulates the complete conversion pipeline from a Regular Expression (Regex) to a Minimized Deterministic Finite Automaton (DFA), featuring step-by-step visualizations and analysis.

🌐 Live Demo

Try it live: https://regx2dfa.vercel.app

Deployed using Vercel — no setup required, just open the link and start converting!

---

Features

• Complete Conversion Pipeline:
  1. Regex Parsing: A recursive descent parser builds an Abstract Syntax Tree (AST) representing the structure and precedence of the regular expression.
  2. Thompson's Construction (ε-NFA): Converts the AST into an Epsilon-Nondeterministic Finite Automaton (ε-NFA).
  3. Subset Construction (DFA): Converts the ε-NFA into an equivalent Deterministic Finite Automaton (DFA) using the powerset construction algorithm.
  4. Hopcroft's Minimization (Min-DFA): Reduces the DFA to its minimal form using partition refinement.
• Interactive Visualizations: Physics-based, interactive graph rendering for every stage using vis-network. Supports dragging, panning, and a dedicated scroll-zoom toggle.
• Transition Tables: Automatically generated state transition tables for the ε-NFA, DFA, and Minimized DFA stages.
• String Tester: An animated string testing module that traces the path of an input string through the Minimized DFA step-by-step, indicating acceptance or rejection.
• Algorithm Explanations: Real-time theoretical context and rules provided for each conversion step.
• Conversion Statistics: Displays state reduction metrics to highlight the effectiveness of the minimization algorithm.
• Premium UI: A modern, fully responsive light theme designed for readability and aesthetic appeal.

---

Supported Regex Syntax

Symbol	Meaning	Example
a-z, 0-9	Literal characters	a, b, 1
(implicit)	Concatenation	ab → a followed by b
|	Union (OR)	a|b → a or b
*	Kleene Star (zero or more)	a*
+	Plus (one or more)	a+
?	Optional (zero or one)	a?
()	Grouping	(a|b)*

---

Example Inputs to Try

Regex	Description
(a|b)*abb	Strings ending in abb
(a|b)*	All strings over {a, b}
a*b*	Zero or more a's followed by zero or more b's
(a|b)*aa(a|b)*	Strings containing aa
a+b?c*	One or more a's, optional b, zero or more c's

---

Project Files

File	Description
index.html	Main structure and UI layout
styles.css	Complete light theme stylesheet
app.js	All algorithms, parsing logic, and UI interactions
README.md	This file

---

Running Locally (Optional)

If you want to run this project on your own machine instead of using the live demo:

1. Clone the repository:

   git clone https://github.com/Ravi-kumar03/regx2dfa.git
   cd regx2dfa

2. Start a local web server:

   python -m http.server 3000

3. Open your browser and go to http://localhost:3000

---

Dependencies

• Vis-Network — Loaded via CDN for interactive automata graph rendering. No local installation needed.

---

Algorithms Used

1. Recursive Descent Parsing — Builds the Abstract Syntax Tree (AST) from the regex string
2. Thompson's Construction — Converts AST to ε-NFA with guaranteed correctness
3. Powerset (Subset) Construction — Determinizes the ε-NFA into a DFA
4. Hopcroft's Algorithm — Minimizes the DFA using partition refinement in O(n log n)

---

Theory of Computation — Regular Expression to Minimized DFA Conversion Simulator