Regular expressions — equivalence with finite automata

4.6.5 · Coding › Theory of Computation

Hum kya prove kar rahe hain?

Yeh ek iff hai, isliye humein do directions chahiye:

Regex → NFA (har pattern ek machine ki tarah banaya ja sakta hai) — Thompson's construction.
FA → Regex (har machine ka behavior ek pattern ki tarah express kiya ja sakta hai) — state elimination.

Kyunki NFA ≡ DFA (subset construction, alag jagah prove kiya gaya), regex ↔ NFA prove karna kaafi hai.

Regex syntax (pehle, taaki hum jaanein hum kya convert kar rahe hain)

Direction 1: Regex → NFA (Thompson's construction)

Formula KAISE — har gadget ko first principles se derive karo

Base cases (sabse chhote patterns):

$\emptyset$ : start $\to$ accept ke beech koi path nahi. Kuch bhi accept nahi karta.
$ε$ : start $ε$ accept. Sirf empty string accept karta hai.
$a$ : start $a$ accept. Sirf "a" accept karta hai.

Inductive cases — maan lo hamare paas pehle se $R, S$ ke liye NFAs $N_{R}$ aur $N_{S}$ hain:

Union $R ∣ S$ . WHY: ek input accept hota hai agar woh $R$ ya $S$ ke liye kaam kare. Toh ek naya start add karo jo $ε$ -branch karke dono mein jaaye, aur ek naya accept jisme dono purane accepts $ε$ -jump karein. Nondeterminism "dono try karta hai."
Concatenation $R S$ . WHY: accept = ek prefix $R$ se match karta hai phir baaki $S$ se match karta hai. Toh $N_{R}$ ke accept ko $N_{S}$ ke start se ek $ε$ -edge se connect karo. $R$ ka purana accept accepting nahi rehta; naya accept = $N_{S}$ ka accept.
Star $R^{*}$ . WHY: $R^{*}$ = zero ya zyada copies of $R$ . Naya start $ε$ naya accept (zero copies) aur naya start $ε$ $N_{R}$ ka start; $N_{R}$ ka accept $ε$ wapas $N_{R}$ ke start pe (repeat) aur naye accept pe (stop).

Figure — Regular expressions — equivalence with finite automata

Direction 2: FA → Regex (state elimination / GNFA)

Formula KAISE — ripping rule (derive karo)

Pehle normalize karo: ek naya start state $s$ add karo jo purane start mein $ε$ se jaaye, aur ek naya accept $f$ jo purane sabhi accepts se $ε$ se aaye. Ab koi bhi doosra state $q$ eliminate karo. Ek path $i \to q \to j$ dekho. Maano:

$R_{i q}$ = label $i \to q$ , $R_{q q}$ = self-loop on $q$ , $R_{q j}$ = label $q \to j$ , $R_{ij}$ = existing $i \to j$ .

$q$ se guzarta hua path jaata hai $i$ , phir $q$ , phir $q$ pe kisi bhi number of times loop karta hai ( $R_{q q}^{*}$ ), phir $j$ pe jaata hai. Jo pehle se seedha $i \to j$ jaata tha, usse combine karo: $R_{ij}^{new} = R_{ij} ∣ R_{i q} R_{q q}^{*} R_{q j} .$ YEH EXACT FORM KYUN: $R_{q q}^{*}$ "zero ya zyada baar $q$ pe spin karo" capture karta hai, concatenation legs ko sequence karta hai, aur $∣$ purane direct route ko ek alternative rakhta hai. Repeat karo jab tak sirf $s, f$ nahi bachta; surviving label $R_{s f}$ poore FA ka regex hai.

Dono directions ko saath mein rakhna

Recall Feynman: 12 saal ke bacche ko explain karo

Socho ek regex ek recipe likhi in words hai ("pehle ek apple, phir koi bhi number of bananas"). Ek finite automaton ek chhota robot hai jo rooms mein chalta hai jaise woh har fruit khata hai aur green light karta hai agar meal match kare. Kleene's theorem kehta hai: koi bhi recipe jo tum likh sako, uske liye ek robot banaya ja sakta hai jo ise check kare — aur kisi bhi robot ka behavior wapas ek recipe ki tarah likha ja sakta hai. Yeh dono ek hi idea ki do languages hain, toh tum hamesha ek ko doosre mein translate kar sakte ho.

Active recall

Kleene's Theorem kehta hai

Ek language regular (regex-describable) hai iff woh ek finite automaton (DFA/NFA) se accept hoti hai.

Equivalence prove karne wali do constructions

Regex→NFA via Thompson's construction; FA→Regex via state elimination (GNFA).

Union

R ∣ S

ka Thompson gadget

Naya start ε-branches

N_{R}

aur

N_{S}

mein; naya accept dono purane accepts se ε ke through reach hota hai.

Concatenation

R S

ka Thompson gadget

N_{R}

ke accept se

N_{S}

ke start tak ε-edge; accept =

N_{S}

ka accept.

Star

R^{*}

ka Thompson gadget

Naya start ε se naye accept tak (zero) aur

N_{R}

ke start tak;

N_{R}

ka accept ε se wapas uske start pe (loop) aur naye accept pe (stop).

State-elimination relabeling rule

R_{ij}^{n e w} = R_{ij} ∣ R_{i q} R_{q q}^{*} R_{q j}

Elimination mein

R_{q q}^{*}

ka matlab

Jis state ko delete kiya ja raha hai us pe zero ya zyada baar loop karo jaane se pehle.

Elimination se pehle fresh start/accept kyun add karo

Taaki start mein koi incoming aur accept mein koi outgoing edges na hon, jisse rip rule hamesha applicable ho.

\emptyset^{*}

ki value

ε

— "kuch bhi nahi ka zero ya zyada baar" empty string hai.

NFA proof kaafi kyun hai (directly DFA nahi)

NFA ≡ DFA by subset construction, toh regex↔NFA se regex↔DFA free mein mil jaata hai.

Kya elimination order language change karta hai

Nahi — alag orders equivalent regexes dete hain (same language), sirf form mein alag.

FA ka Regex:

1 a 2

2 b 2

loop, accept 2

a b^{*}

Connections

Finite Automata — DFA and NFA
Subset Construction — NFA to DFA equivalence
Epsilon-NFA and epsilon-closures
Regular Languages — closure properties
Pumping Lemma for Regular Languages
Lexical analysis and grep — applications