NFA — formal definition, epsilon transitions

4.6.3 · Coding › Theory of Computation

Intuition Badi idea (WHY NFAs exist)

Ek DFA ko har (state, symbol) ke liye exactly ek next state choose karna padta hai. Yeh bahut rigid hai. Ek NFA (Nondeterministic Finite Automaton) uska relaxed cousin hai: ek state se, ek symbol par, yeh kai states mein ja sakta hai, zero states mein ja sakta hai, ya bina koi symbol padhe bhi move kar sakta hai (ek ε-transition).

Hum yeh kyun chahte hain? Kyunki isse machines design karna bahut aasaan ho jaata hai. "Kya string mein ab hai?" ya "Kya yeh 01 par khatam hoti hai?" — tum ek NFA seconds mein sketch kar sakte ho jahan DFA ke liye careful bookkeeping ki zarurat padti. Asli fayda yeh hai: har NFA ko ek equivalent DFA mein convert kiya ja sakta hai, isliye NFAs aur DFAs exactly same class of languages accept karte hain (regular languages). NFAs power mein kuch extra nahi karte lekin design mein mehnat bachate hain.

1. Nondeterminism asal mein kya hai?

2. Formal 5-tuple (scratch se banaya hua)

Hum "guessing + free moves wali machine" ko nail down karna chahte hain. Humen minimally kaun se pieces chahiye?

States ka ek finite collection → use $Q$ kaho.
Input symbols ki alphabet → $Σ$ .
Ek rule jo bataye hum kahan ja sakte hain → transition function $δ$ .
Ek jagah shuru karne ke liye → $q_{0}$ .
Yeh kehne ka tarika ki "tum jeete" → accepting states $F$ .

DFA se bass ek twist hai aur woh hai $δ$ ka output type.

3. ε-closure (free moves handle karne ka tool)

Kyunki ε-moves free hain, koi symbol padhne se pehle/baad machine silently ε-arrows ke saath slide kar sakti hai. Humen free mein reachable saari cheez collect karni hai.

" $q$ khud ko shamil karna" kyun? Zero ε-moves allowed hai — tum hamesha "free mein wahi reh" sakte ho.

4. Extended transition $\hat{δ}$ (puri string run karna)

$δ$ ek symbol handle karta hai. Hum ε-moves ko sahi se fold karte hue puri string $w$ ke liye rule derive karte hain.

Base case: kuch bhi padhne se pehle, tum wahin ho jahan start se ε-moves le jaati hain. $\hat{δ} (q, ε) = ECLOSE (q)$

Inductive step: $w = x a$ (string $x$ phir symbol $a$ ) process karne ke liye:

$R = \hat{δ} (q, x)$ lo — $x$ padhne ke baad states ka set.
Har $r \in R$ se, $a$ padho: $⋃_{r \in R} δ (r, a)$ collect karo.
Phir ε-closure lo ( $a$ consume karne ke baad free slides).

Figure — NFA — formal definition, epsilon transitions

5. Worked examples

6. Common mistakes (steel-manned)

7. Active recall

Recall Khud test karo (answers chhupao)

Ek NFA ke $δ$ ka output type kya hai? → $P (Q)$ , states ka ek set.
NFA $w$ ko kab accept karta hai? → koi ek path: $\hat{δ} (q_{0}, w) \cap F \neq = \emptyset$ .
$q$ ko $ECLOSE (q)$ mein kyun shamil karte hain? → zero ε-moves allowed hain.
Kya $ε \in Σ$ hai? → Nahi.
Kya NFAs DFAs se zyada powerful hain? → Nahi; same language class (regular).

What is the formal 5-tuple of an NFA?

(Q, Σ, δ, q_{0}, F)

with

δ : Q \times (Σ \cup {ε}) \to P (Q)

How does an NFA's

δ

differ from a DFA's?

NFA returns a set (

P (Q)

) and allows

ε

in its domain; DFA returns a single state and has no

ε

Define ε-closure of a state

q

All states reachable from

q

by zero or more ε-transitions, including

q

itself.

When does an NFA accept a string

w

When

\hat{δ} (q_{0}, w) \cap F \neq = \emptyset

— at least one reachable state is accepting.

What is the base case of

\hat{δ}

\hat{δ} (q, ε) = ECLOSE (q)

Write the inductive step of

\hat{δ}

\hat{δ} (q, x a) = ECLOSE (⋃_{r \in \hat{δ} (q, x)} δ (r, a))

ε

a member of

Σ

No; ε only appears in

δ

's domain as

Σ \cup {ε}

What does

δ (q, a) = \emptyset

mean in an NFA?

That branch dies on

a

; it is not an error, other branches may still accept.

Are NFAs strictly more powerful than DFAs?

No — both recognize exactly the regular languages.

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho tum ek maze game khel rahe ho aur kuch doors par tum khud ko clone karke copies ko ek saath kai hallways mein bhej sakte ho. Kuch doors toh secret slides hain jo ek clone ko instantly move kar deti hain bina ek step use kiye (woh hai ε-move). Tum jeet jaate ho agar tumhari koi bhi copy treasure room tak pahunch jaaye. Tumhe saari copies ki zarurat nahi — sirf ek lucky clone kaafi hai. Ek NFA exactly yahi game khelti hai, jahan ek word ke letters steps hain.

Connections

DFA — formal definition — deterministic special case ( $δ$ singletons return karta hai, koi ε nahi).
Subset Construction (NFA to DFA) — prove karta hai NFA = DFA in power.
Regular Languages — exactly woh languages jo NFAs/DFAs accept karte hain.
Regular Expressions — Thompson's construction regexes se ε-NFAs banata hai.
Closure Properties of Regular Languages — union/concat/star ε-NFAs se aasaani se design kiye jaate hain.