Chomsky Normal Form (CNF) — conversion — Hinglish notes

4.6.9 · Coding › Theory of Computation

CNF KYA hai?

Convert KAISE karein — 5-step pipeline (Sipser order!)

Sipser ki textbook mein order hai START → DEL → UNIT → TERM → BIN. Messy ε aur unit rules ko pehle hatao, phir terminals ko clean karo aur binarize karo baad mein.

START — ek fresh start symbol $S_{0} \to S$ add karo (taaki start kabhi right-hand side par na aaye).
DEL — == $ε$ -productions== (nullable variables) eliminate karo.
UNIT — unit productions ( $A \to B$ ) eliminate karo.
TERM — lambe rules mein terminals ko naye variables se replace karo.
BIN — 2 se lambi right-hand sides ko length-2 rules ki chains mein todo.

Step 0 (START): naya start symbol

WHY: CNF mein start symbol ko $ε$ rakhne ki allowed hai. Agar $S$ bhi kisi rule ke right side par aata hai, to deleting/transforming ulajh jaata hai. Ek fresh $S_{0}$ jo sirf purane $S$ ki taraf point kare, start ko "clean" rakhta hai.

Step 1 (DEL): $ε$ -productions hatao

WHY: $A \to ε$ (non-start $A$ ke liye) illegal hai. HOW: saare nullable variables dhundho (jinse $ε$ derive ho sakta hai), phir har rule ke liye, nullable occurrences ke har subset ko chhodne wale versions add karo (lekin kabhi bhi poora RHS empty tak mat delete karo — woh dobara ε-rule bana dega).

Step 2 (UNIT): renames $A \to B$ hatao

WHY: $A \to B$ koi terminal produce nahi karta aur koi branching nahi — bas rename karta hai. HOW: har unit pair $(A, B)$ ke liye (matlab $A \Rightarrow^{*} B$ sirf unit rules use karke), aur har non-unit rule $B \to γ$ ke liye, $A \to γ$ add karo. Phir saari unit rules drop karo.

Step 3 (TERM): terminals ko isolate karo

WHY: $A \to a C$ mein, terminal $a$ illegally variable $C$ ke saath mix hai. $T_{a} \to a$ introduce karo aur $A \to T_{a} C$ likhao. (Ek standalone $A \to a$ pehle se theek hai.)

Step 4 (BIN): lambe rules chop karo

WHY: $A \to B_{1} B_{2} B_{3} B_{4}$ bahut lamba hai. Isko replace karo $A \to B_{1} X_{1}, X_{1} \to B_{2} X_{2}, X_{2} \to B_{3} B_{4} .$ Har naya $X_{i}$ ek fresh variable hai jo "chain ka baaki hissa" rakhta hai.

Figure — Chomsky Normal Form (CNF) — conversion

Worked Example 1 — poori conversion (Sipser order)

Grammar: $S \to A S A ∣ a B, A \to B ∣ S, B \to b ∣ ε$

START. $S_{0} \to S$ add karo. Yeh step kyun? Taaki start kabhi right side par na baithe. Rules: $S_{0} \to S$ ; $S \to A S A ∣ a B$ ; $A \to B ∣ S$ ; $B \to b ∣ ε$ .

DEL. Nullable set: $B \to ε \Rightarrow B$ nullable. $A \to B$ jahan $B$ nullable $\Rightarrow A$ nullable. Koi aur all-nullable RHS nahi. To $N = {A, B}$ . Har rule ko nullable positions ke saare subsets par patch karo (kabhi empty tak nahi):

$S \to A S A$ : nullable positions dono $A$ 's hain. Drop subsets ⟹ $S \to S A ∣ A S ∣ S$ add karo. To $S \to A S A ∣ S A ∣ A S ∣ S$ .
$S \to a B$ : $B$ nullable ⟹ $S \to a$ add karo. To $S \to a B ∣ a$ .
$A \to B$ : $B$ nullable ⟹ $A \to ε$ add hota — drop karo (yeh $S_{0}$ nahi hai). $A \to B$ rakho.
$A \to S$ : rakho (koi nullable symbol nahi).
$B \to b$ : rakho. $B \to ε$ delete karo.

DEL ke baad: $S_{0} \to S$ ; $S \to A S A ∣ S A ∣ A S ∣ S ∣ a B ∣ a$ ; $A \to B ∣ S$ ; $B \to b$ .

UNIT. Unit pairs dhundho (reflexive + transitive closure unit rules $S \to S$ , $A \to B$ , $A \to S$ , $S_{0} \to S$ par):

$(S_{0}, S)$ , aur $S$ ke through kuch aur nahi ( $S$ ka sirf unit rule $S \to S$ hai). $S \to S$ ek trivial self-unit hai, hata diya.
$(A, S)$ , $(A, B)$ .

Ab har variable ke liye, un saare variables ke non-unit bodies collect karo jahan tak woh pahunch sakta hai:

Non-unit bodies of $S$ : ${A S A, S A, A S, a B, a}$ .
Non-unit bodies of $A$ : $A \Rightarrow^{*} B$ se ${b}$ ; $A \Rightarrow^{*} S$ se ${A S A, S A, A S, a B, a}$ .
Non-unit bodies of $B$ : ${b}$ .

Result (unit rules drop kiye):

S_{0} S A B \to A S A ∣ S A ∣ A S ∣ a B ∣ a \to A S A ∣ S A ∣ A S ∣ a B ∣ a \to A S A ∣ S A ∣ A S ∣ a B ∣ a ∣ b \to b

Yeh step kyun? Har rename ko asli productive bodies se replace kar diya jaata hai jinhe woh reach kar sakta tha.

TERM. Terminal $a$ $a B$ mein mixed appear karta hai: $T_{a} \to a$ add karo, $a B \to T_{a} B$ likhao. (Standalone $\to a$ aur $\to b$ waise hi rahenge.)

S_{0}, S A B \to A S A ∣ S A ∣ A S ∣ T_{a} B ∣ a \to A S A ∣ S A ∣ A S ∣ T_{a} B ∣ a ∣ b \to b, T_{a} \to a

BIN. Sirf $A S A$ (length 3) bahut lamba hai. $A_{1} \to S A$ add karo, $A S A \to A A_{1}$ likhao:

S_{0}, S A A_{1} \to A A_{1} ∣ S A ∣ A S ∣ T_{a} B ∣ a \to A A_{1} ∣ S A ∣ A S ∣ T_{a} B ∣ a ∣ b \to S A, B \to b, T_{a} \to a

Yeh step kyun? Ab har rule $A \to B C$ ya $A \to a$ hai — CNF achieve ho gaya. ✓

Worked Example 2 — chhota aur clean

Grammar: $S \to a S b ∣ ab$ . (Koi ε nahi, koi unit rules nahi — DEL aur UNIT kuch nahi karte.)

TERM: $T_{a} \to a$ , $T_{b} \to b$ . Rules: $S \to T_{a} S T_{b} ∣ T_{a} T_{b}$ . Kyun? $a, b$ ko isolate karo.

BIN: $S \to T_{a} S T_{b}$ (length 3): $S \to T_{a} X_{1}$ , $X_{1} \to S T_{b}$ . Kyun? Length-3 ko do length-2 rules mein kato.

Final CNF: $S \to T_{a} X_{1} ∣ T_{a} T_{b}, X_{1} \to S T_{b}, T_{a} \to a, T_{b} \to b .$ Language $= {a^{n} b^{n} : n \geq 1}$ , unchanged. ✓

Forecast-then-Verify

Common mistakes

Flashcards

CNF mein kaun se do production forms allowed hain (start-ε chhodkar)?

A \to B C

(do variables) aur

A \to a

(ek terminal).

CNF mein ε legally kaun sa ek rule produce kar sakta hai?

Sirf start symbol:

S_{0} \to ε

, aur tabhi jab ε language mein ho.

Sipser ke 5 CNF conversion steps ka order kya hai?

START, DEL, UNIT, TERM, BIN.

Sipser mein DEL/UNIT, TERM/BIN se pehle kyun aata hai?

ε- aur unit-removal sirf RHSs ko chhoTa/rename karta hai, to pehle karne se TERM/BIN kabhi undo nahi hota.

Nullable variable define karo.

Ek variable

A

jiske liye

A \Rightarrow^{*} ε

(empty string derive ho sake).

DEL mein

A \to X Y Z

jahan

X, Z

nullable hain, ko kaise patch karte hain?

{X, Z}

ke har subset ko chhodte hue ek rule add karo:

A \to X Y Z ∣ Y Z ∣ X Y ∣ Y

(kabhi empty nahi).

Unit production kya hoti hai aur use kaise hatate hain?

Ek rule

A \to B

(B ek variable); hatao har non-unit body

γ

ke liye

A \to γ

add karke jo unit pair

(A, B)

ke roop mein reachable ho.

CNF useful kyun hai?

Parse trees binary ban jaate hain ⟹ CYK

O (n^{3})

membership aur CFL pumping lemma enable hota hai.

BIN mein

A \to B_{1} B_{2} B_{3}

convert karne par kya milta hai?

A \to B_{1} X_{1}

X_{1} \to B_{2} B_{3}

(ek fresh variable).

Pehle naya start symbol

S_{0}

kyun add karte hain?

Taaki start symbol kisi bhi right-hand side par na aaye, baad ke steps clean rahein.

Recall Feynman: 12-saal ke bache ko explain karo

Socho LEGO instructions jahan har step mein sirf EK cheez ho sakti hai: ya to do bade blocks snap karo, ya ek single colored tile lagao. Koi giant complicated steps allowed nahi. CNF ek messy building manual ko is baby-simple style mein rewrite karta hai. Bana hua tower bilkul wahi rahega — lekin ab ek robot steps bahut fast follow kar sakta hai aur yeh bhi check kar sakta hai ki koi diya hua tower bana sakta hai ya nahi. Hum clean karte hain: ek fresh "start" block deke, "kuch mat banao" steps hatake, "is block ko doosra naam se bolo" lazy steps hatake, phir loose colored tiles ko named blocks se badal ke, aur aakhir mein lambe steps ko pairs mein chop karke.