NFA to DFA Conversion

Subset Construction Algorithm

Goal

Convert NFA $N = (Q_N, \Sigma, \delta_N, q_0, F_N)$ to equivalent DFA $D = (Q_D, \Sigma, \delta_D, q_0', F_D)$.

Key Idea

Each DFA state represents a set of NFA states.

Epsilon Closure

The epsilon closure of a state $q$: $\epsilon\text{-closure}(q) = \{q\} \cup \{p \mid p \text{ reachable from } q \text{ via } \epsilon\text{-transitions}\}$

For a set $S$: $\epsilon\text{-closure}(S) = \bigcup_{q \in S} \epsilon\text{-closure}(q)$

The Algorithm

Input: NFA N = (Q, Σ, δ, q₀, F)
Output: Equivalent DFA D

1. Start state of D: q₀' = ε-closure({q₀})

2. Initialize: Q_D = {q₀'}, unmarked
   
3. While there is an unmarked state S in Q_D:
       Mark S
       For each symbol a ∈ Σ:
           T = ε-closure(δ(S, a))  // δ(S,a) = ∪_{q∈S} δ(q,a)
           If T ∉ Q_D:
               Add T to Q_D (unmarked)
           Add transition δ_D(S, a) = T

4. Accept states: F_D = {S ∈ Q_D | S ∩ F ≠ ∅}

Example

NFA

Accepts strings ending in "01":

State	$\epsilon$	0	1
$q_0$	-	$\{q_0, q_1\}$	$\{q_0\}$
$q_1$	-	-	$\{q_2\}$
$q_2$ (accept)	-	-	-

Step-by-Step Conversion

Step 1: Start state = $\epsilon$-closure($\{q_0\}$) = $\{q_0\}$

Step 2: Process $\{q_0\}$:

• On 0: $\delta(\{q_0\}, 0) = \{q_0, q_1\}$
• On 1: $\delta(\{q_0\}, 1) = \{q_0\}$

Step 3: Process $\{q_0, q_1\}$:

• On 0: $\delta(\{q_0, q_1\}, 0) = \{q_0, q_1\}$
• On 1: $\delta(\{q_0, q_1\}, 1) = \{q_0, q_2\}$

Step 4: Process $\{q_0, q_2\}$:

• On 0: $\{q_0, q_1\}$
• On 1: $\{q_0\}$

Resulting DFA

DFA State	0	1	Accept?
$\{q_0\}$	$\{q_0, q_1\}$	$\{q_0\}$	No
$\{q_0, q_1\}$	$\{q_0, q_1\}$	$\{q_0, q_2\}$	No
$\{q_0, q_2\}$	$\{q_0, q_1\}$	$\{q_0\}$	Yes

Handling Epsilon Transitions

Extended Move Function

For set $S$ and symbol $a$: $\text{move}(S, a) = \{q \mid p \in S, q \in \delta(p, a)\}$

Then: $\delta_D(S, a) = \epsilon\text{-closure}(\text{move}(S, a))$

Example with Epsilon

NFA with $\epsilon$-transition:

State	$\epsilon$	a	b
$q_0$	$\{q_1\}$	-	-
$q_1$	-	$\{q_2\}$	-
$q_2$ (accept)	-	-	$\{q_2\}$

Start state: $\epsilon$-closure($\{q_0\}$) = $\{q_0, q_1\}$

Transitions from $\{q_0, q_1\}$:

• On a: move = $\{q_2\}$, $\epsilon$-closure = $\{q_2\}$
• On b: move = $\emptyset$, $\epsilon$-closure = $\emptyset$

DFA Minimization

After conversion, minimize the DFA.

Algorithm (Table-Filling / Myhill-Nerode)

1. Partition states: initially by accept/non-accept
2. Refine: split groups where transitions lead to different groups
3. Repeat until stable
4. Each final group becomes one state

Example

DFA with states $\{A, B, C, D, E\}$:

1. Initial: $\{A, B, C\}$ (non-accept), $\{D, E\}$ (accept)
2. Check transitions; split if needed
3. Continue until stable

Complexity

Worst Case

NFA with $n$ states → DFA with up to $2^n$ states.

Example: Exponential Blowup

NFA for "$(a|b)^* a (a|b)^{n-1}$" (n-th from last is 'a')

• NFA: $O(n)$ states
• Minimal DFA: $2^n$ states

Lazy Evaluation

On-Demand Construction

Build DFA states only when needed:

1. Start with initial state
2. When transitioning to unseen state, compute it
3. Cache computed states

Useful when only testing specific inputs.

Applications

Lexical Analysis

Compilers convert regex → NFA → DFA for tokenizing.

Pattern Matching

DFA enables $O(n)$ matching for string of length $n$.

Network Intrusion Detection

Pattern matching on network traffic.

Comparison

Aspect	NFA	DFA
States	Fewer	Up to exponentially more
Transitions	Multiple per symbol	Exactly one per symbol
Simulation	Backtracking/parallel	Linear scan
Construction	Easy from regex	May be expensive