ToolSphere
Back to all articles
Computer Science

NFA to DFA: The Subset Construction

2026-07-2810 min read

Try it: free NFA to DFA Converter

Turn an NFA into a DFA with the subset construction shown

Open →

Introduction to Subset Construction

The Subset Construction (or powerset construction) algorithm converts a Nondeterministic Finite Automaton (NFA) into an equivalent Deterministic Finite Automaton (DFA). Since an NFA can exist in multiple states simultaneously, each state in the new DFA represents a subset of states from the original NFA.

Epsilon-closures (ε-closure)

Before translating transitions, calculate the ε-closure of each state subset. The ε-closure of a state q is the set of every state reachable from q using only epsilon (ε) transitions, including q itself:

ε-closure(q) = { p : p can be reached from q by zero or more ε-moves }

Step-by-step transition table example

Take the NFA for strings over {a, b} that end in ab: states q₀ (start), q₁ and q₂ (accepting), with q₀ → q₀ on a or b, q₀ → q₁ on a, and q₁ → q₂ on b. It has no ε-moves, so each closure is just the state itself.

DFA state NFA state subset On 'a' On 'b'
A (start) {q₀} {q₀, q₁} (B) {q₀} (A)
B {q₀, q₁} {q₀, q₁} (B) {q₀, q₂} (C)
C (accepting) {q₀, q₂} {q₀, q₁} (B) {q₀} (A)

C is accepting because its subset contains the NFA's accepting state q₂. Only 3 of the 2³ = 8 possible subsets are reachable, which is typical: you build the table only for subsets you actually reach from the start.

Frequently Asked Questions

Why do we convert NFA to DFA?

DFAs are straightforward to implement in silicon and software (typically a simple two-dimensional array lookup), making them highly suitable for lexical analyzers like Lex and Flex.

Next Steps

Use our NFA to DFA Converter to automatically calculate closures and transition graphs.

Use the Finite Automata Simulator (NFA/DFA) to experiment with finite-automaton examples. For a related walkthrough, read NFA vs DFA: The Difference Explained.

Looking for other tools?

Explore ToolSphere Homepage →