NFA to DFA conversion — subset construction

4.6.4 · Coding › Theory of Computation

WHAT is the problem?

WHY yeh possible hai? Kyunki NFA aur DFA dono exactly regular languages hi recognize karte hain — inki power equal hai. NFA likhne mein zyada convenient hai; DFA chalane mein zyada mechanical hai.

The two helper operations

HOW — the algorithm

Figure — NFA to DFA conversion — subset construction

Worked Example 1 (no ε)

NFA over $Σ = {a, b}$ , states ${q_{0}, q_{1}}$ , start $q_{0}$ , final ${q_{1}}$ : $δ_{N} (q_{0}, a) = {q_{0}, q_{1}}$ , $δ_{N} (q_{0}, b) = {q_{0}}$ , $δ_{N} (q_{1}, b) = {q_{1}}$ . (Yeh un strings ko accept karta hai jisme ek $a$ ke baad eventually ek $b$ ho… chaliye bas build karte hain.)

DFA state	on $a$	on $b$
$A = {q_{0}}$ (start)	${q_{0}, q_{1}} = B$	${q_{0}} = A$
$B = {q_{0}, q_{1}}$ (accept)	${q_{0}, q_{1}} = B$	${q_{0}, q_{1}} = B$

$A a B$ kyun? MOVE $({q_{0}}, a) = {q_{0}, q_{1}}$ , koi ε nahi toh ECLOSE aise hi chhod deta hai. Naya state → ise $B$ kehte hain. $B$ accepting kyun hai? $B \cap F = {q_{0}, q_{1}} \cap {q_{1}} = {q_{1}} \neq = \emptyset$ . ✔ $B b B$ kyun? MOVE $({q_{0}, q_{1}}, b) = {q_{0}} \cup {q_{1}} = {q_{0}, q_{1}} = B$ .

Possible $2^{2} = 4$ subsets mein se sirf 2 reachable hain — hum unreachable wale kabhi list nahi karte.

Worked Example 2 (with ε)

NFA: states ${0, 1, 2}$ , start $0$ , final ${2}$ , $Σ = {a}$ . $δ (0, ε) = {1}$ , $δ (1, a) = {2}$ , $δ (2, ε) = {1}$ .

Step 1 — start: $q_{0}^{'} = ECLOSE ({0}) = {0, 1}$ . Kyun? $0$ se ek ε-edge $1$ par jaati hai; $1$ se koi nahi. Ise $A = {0, 1}$ kaho.

Step 2 — $A$ on $a$ : MOVE $({0, 1}, a) = {2}$ (sirf $1$ ke paas $a$ -edge hai). Phir ECLOSE $({2}) = {2, 1} = {1, 2}$ (ε-edge $2 \to 1$ ). $B = {1, 2}$ kaho.

Step 3 — $B$ on $a$ : MOVE $({1, 2}, a) = {2}$ , ECLOSE → ${1, 2} = B$ . Self-loop.

DFA state	on $a$	accept?
$A = {0, 1}$ (start)	$B$	${0, 1} \cap {2} = \emptyset$ → no
$B = {1, 2}$	$B$	$2$ hai → yes

Toh DFA $a, aa, aaa, \dots$ yaani $a^{+}$ accept karta hai. "aa" trace karo: $A a B a B$ (accept). ✔ "" trace karo: $A$ par rehta hai, reject. ✔

Common mistake Steel-manned common errors

Mistake 1: Start state par ε-closure bhool jaana. Kyun sahi lagta hai: "NFA $q_{0}$ par start hota hai, toh DFA ${q_{0}}$ par start hona chahiye." Saaf aur obvious. Kyun galat hai: NFA kuch bhi padhne se pehle ε-edges ke saath silently move kar sakta hai. Fix: start $= ECLOSE ({q_{0}})$ .

Mistake 2: MOVE ke baad nahi balki pehle ε-closure apply karna. Kyun sahi lagta hai: start par close kar liya, kaam ho gaya. Fix: har step mein sahi order $ECLOSE (MOVE (S, a))$ hai — har move ke baad, har baar close karo.

Mistake 3: Pehle se saare $2^{n}$ subsets generate karna. Kyun sahi lagta hai: worst case $2^{n}$ hai, toh "sab list kar do." Fix: sirf woh subsets banao jo start state se reachable hain. Aam taur par kaafi kam hote hain.

Mistake 4: Kisi state ko accepting tab hi mark karna jab woh NFA final state ke barabar ho. Kyun sahi lagta hai: "final matlab final." Fix: accept karo agar subset mein koi bhi final state ho ( $S \cap F \neq = \emptyset$ ) — NFA succeed karta hai agar koi ek path accept kare.

Mistake 5: Dead state $\emptyset$ bhool jaana. Agar MOVE empty set de, phir bhi ek (trap) state chahiye jo khud par loop kare aur reject kare — warna DFA transition undefined ho jata hai.

Recall Feynman: explain to a 12-year-old

Socho ek aisa maze hai jahan kuch forks par ek magic robot copies mein split ho sakta hai aur ek saath har path try karta hai. Woh NFA hai. Ek normal robot (DFA) split nahi ho sakta — woh ek path chalata hai. Toh uski jagah, normal robot ek notebook carry karta hai jisme likha hota hai "magic robot abhi kin-kin rooms mein khada ho sakta hai." Har baar jab woh ek letter padhta hai, woh poori list ek saath update karta hai. Agar list mein koi bhi room exit hai, woh "Accepted!" chilla deta hai. Notebook ka content = ek DFA state. Kyunki rooms ki sirf finite possible lists hain, robot kabhi hamesha ke liye nahi kho sakta.

Flashcards

Subset construction mein DFA ki ek state kya hoti hai?

NFA states ka ek set (subset) — woh "cloud" of states jahan NFA abhi ho sakta hai.

Ise powerset/subset construction kyun kehte hain?

DFA states

Q

ke subsets hain, power set

P (Q)

se liye gaye.

DFA start state ka formula?

q_{0}^{'} = ECLOSE ({q_{0}})

DFA transition ka formula?

δ_{D} (S, a) = ECLOSE (MOVE (S, a))

DFA subset-state accepting kab hoti hai?

Jab usme kam se kam ek NFA final state ho:

S \cap F \neq = \emptyset

ECLOSE(S) kya hai?

Woh saari states jo S se sirf ε-transitions use karke reachable hain (S khud bhi shamil hai).

MOVE(S,a) kya hai?

q \in S

par

δ_{N} (q, a)

ka union —

a

padhne par reachable states.

n

-state NFA se DFA states ki maximum number?

2^{n}

(subsets ki number); usually kam reachable hote hain.

Subset construction hamesha terminate kyun karta hai?

Sirf

2^{n}

possible subsets hain, isliye finite number of DFA states ban sakti hain.

Empty set

\emptyset

ka kya role hai?

Dead/trap state — koi NFA state alive nahi, toh reject karta hai aur khud par loop karta hai.

Har step mein operations ka sahi order kya hai?

Pehle MOVE, phir ECLOSE: ECLOSE(MOVE(S,a)).

Kya NFA aur DFA same languages recognize karte hain?

Haan — dono exactly regular languages recognize karte hain.

Connections

Finite Automata — DFA basics
Finite Automata — NFA and ε-NFA
Regular Expressions to NFA — Thompson's construction
DFA Minimization — Myhill–Nerode
Power Set and Subsets
Closure Properties of Regular Languages
Pumping Lemma for Regular Languages