Neural Sync Active

NFA to DFA Conversion — Subset Construction

Registry Synced

NFA to DFA Conversion — Subset Construction

1102 words

6 min read

Reading compass

Now · 🎯 Learning Objectives

NFA to DFA Conversion — Subset Construction

🎯 Learning Objectives

Compute ε-closure for NFA states
Apply subset construction algorithm
Trace conversion step by step
Minimize the resulting DFA
Compare NFA and DFA tradeoffs

1. ε-Closure

1.1 Definition

ε-closure(q) = set of states reachable from q using only ε-transitions (including q itself). Algorithm:

Add q to closure
While there's a state s in closure with an ε-transition to t not in closure:
- Add t to closure

1.2 Worked Example

NFA: q0 --ε→ q1 --ε→ q2, q0 --a→ q3 ε-closure(q0): {q0, q1, q2} (q0 itself, q0→ε→q1, q1→ε→q2) ε-closure(q1): {q1, q2} ε-closure(q2): {q2} ε-closure(q3): {q3}

2. Subset Construction Algorithm

Given NFA N = (Q, Σ, δ, q0, F), construct DFA D = (Q', Σ, δ', q0', F'):

q0' = ε-closure(q0)
For each DFA state (set of NFA states) and each input symbol a:
- Compute next = ε-closure(δ(q, a) for all q in current state)
- If next is new, add to Q'
DFA final states = any set containing an NFA final state

3. Full Tracing Example

NFA: (Diagram) NFA Definition:

States: Q = {q0, q1, q2, q3, q4}
Alphabet: Σ = {a, b}
Start: q0
Final: q3
Transitions:
- δ(q0, ε) = {q1}, δ(q0, a) = {q3}
- δ(q1, ε) = {q2}, δ(q1, b) = {q4}
- δ(q2, a) = {q0}
- δ(q4, a) = {q4}, δ(q4, b) = {q4}

3.1 ε-Closures

State	ε-Closure
q0	{q0, q1, q2}
q1	{q1, q2}
q2	{q2}
q3	{q3}
q4	{q4}

3.2 DFA Construction Tracing

Step 1: Start state = ε-closure(q0) = {q0, q1, q2} → A Step 2: Compute transitions for A on 'a' and 'b': A on 'a':

δ(q0, a) = {q3}
δ(q1, a) = { } (no transition from q1 on a)
δ(q2, a) = {q0}
ε-closure({q3, q0}) = {q3} ∪ {q0, q1, q2} = {q0, q1, q2, q3} → B A on 'b':
δ(q0, b) = { }
δ(q1, b) = {q4}
δ(q2, b) = { }
ε-closure({q4}) = {q4} → C Step 3: Compute transitions for B and C: B = {q0, q1, q2, q3} on 'a':
δ(q0, a)={q3}, δ(q2, a)={q0}
ε-closure({q3, q0}) = {q0, q1, q2, q3} = B B on 'b':
δ(q1, b)={q4}
ε-closure({q4}) = {q4} = C C = {q4} on 'a':
δ(q4, a)={q4}
ε-closure({q4}) = {q4} = C C on 'b':
δ(q4, b)={q4}
ε-closure({q4}) = {q4} = C

3.3 Resulting DFA

State	on 'a'	on 'b'	Final?
A = {q0,q1,q2}	B	C	No
B = {q0,q1,q2,q3}	B	C	Yes (q3 ∈ B)
C = {q4}	C	C	No

(Diagram)

4. DFA Minimization After Conversion

Apply table-filling to the DFA with states {A, B, C}:

Mark (A, B): B is final, A is not → distinguishable
Mark (A, C): neither final → check transitions
- δ(A,a)=B, δ(C,a)=C → (B,C) unmarked so far
- δ(A,b)=C, δ(C,b)=C → (C,C) same
- (B,C) will be checked...
Mark (B, C): B is final, C is not → distinguishable Result: All states distinguishable → DFA is already minimal.

5. Common Pitfalls

Pitfall: Forgetting ε-Closure After Each Transition

The mistake: Computing δ(state, a) but not computing ε-closure of the result. Correct approach: After following δ(q, a) for each q in current set, ALWAYS compute ε-closure of the union.

6. Key Concepts Reference

Step	Description	Example
ε-closure	All states reachable via ε	ε-closure(q0) = {q0,q1,q2}
Subset construction	Each DFA state = set of NFA states	A = {q0,q1,q2}
Transition	δ'(S, a) = ε-closure(∪ δ(q, a))	A--a→B
Final states	Sets containing NFA final	B = {q0,q1,q2,q3}

7. 📝 Practice Questions

Q1: Compute ε-closure for: q0 →ε→ q1 →ε→ q2, q1 →a→ q3.

Answer: ε-closure(q0) = {q0, q1, q2} ε-closure(q1) = {q1, q2} ε-closure(q2) = {q2} ε-closure(q3) = {q3} Q2: From the worked example, what strings does the DFA accept?

Answer: Any string that reaches state B (which contains final NFA state q3). From the DFA, B is reached by any 'a' (goes to B from A) followed by anything (B loops on a, goes to C on b but can return...). Actually B is reached by: any string with at least one 'a' and no 'b' after the last 'a'... Let me trace: from A, 'a' → B. From B, 'a' → B, 'b' → C. From C, 'a' or 'b' → C (dead state). So accepted strings are: must start with 'a' (or reach from A via 'a'), and once a 'b' appears, no more 'a's can follow.

Actually simpler: the DFA accepts strings that end in 'a' and have no 'b' after some point. More precisely: strings that have at least one 'a' or more intuitive: strings that reach B = {q0,q1,q2,q3} which is the accepting state. The path A--a→B is the only way to accept. Once in B, 'a' stays in B, 'b' goes to C (dead). So accepted strings = strings with at least one 'a' and no 'b' after the last 'a' that leads to B... Actually accepted strings = any string that has an 'a' processed from a state that has an outgoing 'a' transition to q3. This is getting complex — the DFA accepts strings where the last character before the string ends (or before the first 'b') is 'a' that comes from certain states.

Let me just test: "a" → A--a→B → accept. "aa" → A--a→B--a→B → accept. "ab" → A--a→B--b→C → reject. "b" → A--b→C → reject. So it accepts strings consisting ONLY of 'a's (one or more). Q3: An NFA with n states can produce a DFA with how many states?

Answer: Worst case: 2^n states (every subset of NFA states). Example: NFA for language of strings ending in a specific pattern. In practice, many subsets are unreachable, giving far fewer states. The worked example: 5 NFA states → 3 DFA states. Q4: Why do we need ε-closure in subset construction?

Answer: ε-transitions are spontaneous — they happen without consuming input. After reading a symbol, the NFA can be in ANY state reachable via ε-transitions from the target states. ε-closure captures all these possibilities. Without it, we'd miss states reachable through ε-chains, causing the DFA to reject strings the NFA accepts.

8. 🔗 Cross-References

Week 1 - Finite Automata: NFA/DFA basics
Week 3 - DFA Minimization: Minimizing the result
BSCS4032 (Compiler Design): Lexical analysis Join Discord PreviousDFA & NFANextRegular Expressions & Pumping Lemma