Master the subset construction algorithm through interactive step-by-step visualization. Watch every ε-closure, move, and DFA state form in real time.
subset-construction.js
ALGOSubsetConstruction(NFA):// 1. Start from the initial state q₀ ←ε-closure({ NFA.start }) queue ← [ q₀ ]WHILE queue is not empty: S ← queue.dequeue()FOR EACH symbol a in Σ (alphabet):// Follow 'a', then close over ε-moves T ←ε-closure( move(S, a) )IF T is a new state: queue.enqueue( T ) DFA.addEdge( S ─a→ T )RETURN DFA
Everything You Need to Master the Conversion
From drawing your NFA to receiving a complete, verified DFA — every step explained visually
Step-by-Step NFA → DFA
The core feature. Watch the subset construction algorithm run one step at a time — each ε-closure, each move, and every new DFA state explained in plain English.
Open Converter →
ε-Closure Computation
See exactly which NFA states are reachable via epsilon transitions at every step. States glow and highlight as the BFS closure expands — nothing is hidden.
Dual Graph Visualization
NFA and DFA graphs displayed side by side. Watch the DFA grow state-by-state as the algorithm processes each NFA subset — both graphs update in sync.
Live DFA Transition Table
The DFA transition table builds row-by-row and cell-by-cell as the algorithm runs. New entries flash to show exactly what was just computed.
Draw Your Own NFA
Use the interactive Simulator to draw any NFA — add states, drag them, draw ε-transitions, mark accepting states — then send it straight to the converter.
Test the Resulting DFA
After conversion, send the generated DFA directly to the Simulator and test it against input strings — or export it as JSON to use in your own projects.
See the Subset Construction in Action
Pick a preloaded NFA, press Convert, and step through every stage of the algorithm — at your own pace.
Automaton Simulator
Draw an NFA here, then click NFA→DFA to convert it step-by-step
Tools
Alphabet
Comma-separated symbols (no ε)
Actions
NFA ready to convert
0 states0 transitionsno accept states
DFA ready to minimize
0 states0 transitions
abab
Ready
Current: -
Transition Table
State
a
b
Statistics
States0
Transitions0
Start State-
Accept States-
⚠ Incomplete DFA — missing transitions
Instructions
1.Select "State" tool and click canvas to add states
2.Select "Edge" tool, click source then target (or same state for self-loop)
3.Mark start and accepting states
4.Enter input string and run simulation
Theory of Automata · Complete Reference
NFA → DFA Conversion — Theory & Examples
Everything you need to understand the subset construction algorithm, from first principles to worked examples.
D
Deterministic Finite Automaton
A DFA is a 5-tuple (Q, Σ, δ, q₀, F) where for every state and every input symbol there is exactly one next state — directly implementable as a table lookup.
Formal Definition
Q — finite set of states
Σ — input alphabet (no ε)
δ : Q × Σ → Q — total transition
q₀ ∈ Q — start state
F ⊆ Q — accept states
Key Properties
Exactly one transition per symbol
No ε transitions
Always halts — no ambiguity
O(n) simulation time
Used In
Lexers & regex engines
Network routers
Hardware circuits
Compiler tokenizers
N
Non-deterministic Finite Automaton
An NFA is also a 5-tuple, but the transition function maps to a set of states — zero, one, or many — and allows ε transitions that consume no input.
Formal Definition
Q — finite set of states
Σ — input alphabet
δ : Q × (Σ∪{ε}) → P(Q)
q₀ ∈ Q — start state
F ⊆ Q — accept states
An NFA accepts a string if at least one computation path reaches an accept state.
Key insight: NFA and DFA recognize exactly the same languages — the regular languages. The subset construction proves their equivalence.
ε
ε-Closure — The Core Operation
The ε-closure of a set S is all states reachable from any state in S by following zero or more ε-transitions — without consuming any input.
BFS Algorithm
Add all states in S to closure + queue
While queue not empty: pop state q
For each ε-transition q→r: add r if new
Return closure
Worked Example — ε-closure({q0})
ε-transitions: q0→q1, q1→q2
Step
Queue
Closure
Action
Init
{q0}
{q0}
Start
1
{q1}
{q0,q1}
q0→ε→q1
2
{q2}
{q0,q1,q2}
q1→ε→q2
3
{ }
{q0,q1,q2}
Done ✓
Result {q0,q1,q2} becomes the first DFA state.
S
Subset Construction Algorithm
Converts an NFA with n states into an equivalent DFA. Each DFA state represents a subset of NFA states — worst case 2ⁿ DFA states, but usually far fewer.
Complete Algorithm
Init: q₀' = ε-closure({q₀NFA}) → add to worklist
Loop: Take DFA state S from worklist
For each a ∈ Σ: compute ε-closure(move(S,a)) = T
If T is new → add to DFA + worklist; record δ'(S,a)=T
Accept: S is accepting iff S ∩ FNFA ≠ ∅
Stop when worklist is empty
Key formula: δ'(S, a) = ε-closure(move(S, a)) Applied for every DFA state S and every symbol a ∈ Σ
①
Example — Strings ending in "ab"
NFA — 3 states, alphabet {a,b}
State
a
b
→ q0
{q0,q1}
{q0}
q1
—
{q2}
* q2
—
—
Conversion steps
A={q0} → on a: {q0,q1}=B, on b: {q0}=A
B={q0,q1} → on a: {q0,q1}=B, on b: {q0,q2}=C ✓accept
C={q0,q2} → on a: {q0,q1}=B, on b: {q0}=A
Resulting DFA
DFA
Subset
a
b
→ A
{q0}
B
A
B
{q0,q1}
B
C
* C
{q0,q2}
B
A
②
Example — ε-NFA for (a|ε)b*
Accepts strings that are just b's, or a followed by any number of b's.
NFA — 3 states, alphabet {a,b,ε}
State
a
b
ε
→ q0
{q1}
—
{q1}
q1
—
{q1}
{q2}
* q2
—
—
—
Key ε-closures
ε-closure({q0}) = {q0,q1,q2} — q0→ε→q1→ε→q2
ε-closure({q1}) = {q1,q2} — q1→ε→q2
Resulting DFA
DFA
Subset
a
b
→ * A
{q0,q1,q2}
B
B
* B
{q1,q2}
Dead
B
Dead
∅
Dead
Dead
A is the start state and already accepting — the empty string ε is in the language, as expected for (a|ε)b*.
≡
NFA vs DFA — Side-by-Side Comparison
Property
NFA
DFA
Transitions per symbol
0, 1, or many states
Exactly 1 state
Epsilon (ε) transitions
✓ Allowed
✗ Not allowed
Transition function
Q×(Σ∪{ε}) → P(Q)
Q×Σ → Q
Acceptance
Any path reaches F
Unique path reaches F
Design complexity
Often simpler to design
Can be complex to design
Simulation cost
Expensive — track all paths
Cheap — one state at a time
Number of states
n states
Up to 2ⁿ (usually fewer)
Expressive power
Identical — both recognize exactly the Regular Languages
?
Why Convert NFA to DFA?
Practical Reasons
›Efficient execution: DFAs run in O(n) time. NFAs track many states simultaneously.
›Regex compilation: Most engines convert regex → NFA → DFA for fast matching.
›Lexical analysis: Compiler lexers use DFAs to tokenize source code at high speed.
›Hardware: DFAs map directly to lookup tables and digital circuits.
Theoretical Reasons
›Equivalence proof: Constructively proves NFA ≡ DFA in expressive power.
›Minimisation: DFA minimisation gives the unique smallest machine for a language.
›Closure properties: Complement is trivial on DFAs, complex on NFAs.
›Decision procedures: Emptiness, membership, equivalence easier on DFAs.
!
Common Mistakes & Pitfalls
Forgetting ε-closure of start state
The first DFA state is ε-closure({q₀}), not just {q₀}. It may include many states reached by ε-hops before any input.
Skipping ε-closure after move
After move(S,a) you must always take ε-closure of the result. Skipping produces a wrong DFA.
Not recognising duplicate DFA states
{q0,q1} and {q1,q0} are the same subset. Always sort and canonicalise before checking.
Missing dead/trap states
When move(S,a)=∅ add a dead state (∅) with self-loops on all symbols.
Wrong accept state identification
A DFA state is accepting if its subset contains at least one NFA accept state — not all of them.
✓
Quick Reference — Subset Construction Checklist
Before you start:
During construction:
Accepting states:
Completion check:
About Automata Lab
Automata Lab is an interactive web-based platform designed to simulate and visualize fundamental concepts of Theory of Automata and Formal Languages.
Purpose
The current version focuses on NFA to DFA conversion and simulation Implemented with detailed step-by-step visualization of subset construction.This serves as a foundational module within the broader vision of the platform
What You Can Do
Work with the NFA → DFA conversion module using step-by-step subset construction
Visualize ε-closure expansions and move operations on highlighted NFA graphs
Observe how DFA states and transition tables are built in real time
Design and simulate custom automata using the graphical simulator
Test automata behavior with input strings through animated execution
Import and export automata configurations for experimentation
Technology
HTML5 CanvasVanilla JavaScriptSubset Construction AlgorithmTailwind CSS
Built with 💗 by Saurabh Raj Shekhar CSE Depart. NSUT
Version 1.0 - Automata Lab
NFA → DFA Converter
Subset Construction — step-by-step visualization
Examples:
Subset Construction Algorithm
1
ε-closure of start state
Becomes the first DFA state.
2
Compute move(S, a)
For each DFA state & symbol.
3
ε-closure of move result
Gives the complete next state.
4
Add new DFA states
If unseen, add to worklist.
5
Mark accept states
DFA state is accepting if it contains any NFA accept state.
6
Repeat until complete
At most 2ⁿ DFA states for n NFA states.
1×
0 / 0←→Space
Ready
Select an example and press Convert
The subset construction algorithm converts any NFA to an equivalent DFA. Choose an example above, then press Convert Step-by-Step.