Chomsky Normal Form (CNF) — conversion — Coding notes

WHAT is CNF?

HOW to convert — the 5-step pipeline (Sipser order!)

In Sipser's textbook the order is START → DEL → UNIT → TERM → BIN. Remove the messy ε and unit rules first, then clean up terminals and binarize last.

START — add a fresh start symbol $S_0 \rightarrow S$ (so the start never appears on a right-hand side).
DEL — eliminate == $\varepsilon$ -productions== (nullable variables).
UNIT — eliminate unit productions ( $A \rightarrow B$ ).
TERM — replace terminals inside long rules with new variables.
BIN — break right-hand sides longer than 2 into chains of length-2 rules.

Step 0 (START): new start symbol

WHY: CNF lets the start symbol have $\varepsilon$ . If $S$ also appears on the right of some rule, deleting/transforming gets tangled. A fresh $S_0$ that only points to old $S$ keeps the start "clean."

Step 1 (DEL): remove $\varepsilon$ -productions

WHY: $A \rightarrow \varepsilon$ (for non-start $A$ ) is illegal. HOW: find all nullable variables (those that can derive $\varepsilon$ ), then for every rule, add versions with each subset of the nullable occurrences omitted (but never delete the entire RHS down to nothing — that would re-create an ε-rule).

Formula Nullable set

$N$ — derived from scratch Define $N$ = smallest set such that:

if $A \rightarrow \varepsilon$ , then $A \in N$ ;
if $A \rightarrow Y_1 Y_2 \dots Y_k$ and every $Y_i \in N$ , then $A \in N$ . Compute by fixed-point iteration until $N$ stops growing.

General patching rule. For a rule $A \rightarrow X_1 X_2 \dots X_k$ , let $P=\{i : X_i \in N\}$ be the positions of nullable symbols. Add a production for every subset $D \subseteq P$ of dropped positions (keep the symbols not in $D$ ), except the empty-RHS case. Example: $A \rightarrow X\,Y\,Z$ with $X,Z$ nullable ( $Y$ not) gives $A \rightarrow XYZ \mid YZ \mid XY \mid Y.$ Then delete every bare $A \rightarrow \varepsilon$ (unless $A=S_0$ ).

Step 2 (UNIT): remove renames $A \rightarrow B$

WHY: $A \rightarrow B$ produces no terminal and no branching — it just renames. HOW: for every unit pair $(A,B)$ (meaning $A \Rightarrow^* B$ using only unit rules), and every non-unit rule $B \rightarrow \gamma$ , add $A \rightarrow \gamma$ . Then drop all unit rules.

Step 3 (TERM): isolate terminals

WHY: In $A \rightarrow aC$ , the terminal $a$ is illegally mixed with variable $C$ . Introduce $T_a \rightarrow a$ and rewrite $A \rightarrow T_a C$ . (A standalone $A\to a$ is already fine.)

Step 4 (BIN): chop long rules

WHY: $A \rightarrow B_1 B_2 B_3 B_4$ is too long. Replace by $A \rightarrow B_1 X_1,\quad X_1 \rightarrow B_2 X_2,\quad X_2 \rightarrow B_3 B_4.$ Each new $X_i$ is a fresh variable holding "the rest of the chain."

Figure — Chomsky Normal Form (CNF) — conversion

Worked Example 1 — full conversion (Sipser order)

Grammar: $S \rightarrow ASA \mid aB,\quad A \rightarrow B \mid S,\quad B \rightarrow b \mid \varepsilon$

START. Add $S_0 \rightarrow S$ . Why this step? So the start never sits on a right side. Rules: $S_0\to S$ ; $S \to ASA \mid aB$ ; $A \to B \mid S$ ; $B \to b \mid \varepsilon$ .

DEL. Nullable set: $B \to \varepsilon \Rightarrow B$ nullable. $A \to B$ with $B$ nullable $\Rightarrow A$ nullable. No other all-nullable RHS. So $N=\{A,B\}$ . Patch each rule over all subsets of nullable positions (never down to empty):

$S \to ASA$ : nullable positions are the two $A$ 's. Drop subsets ⟹ add $S\to SA \mid AS \mid S$ . So $S \to ASA \mid SA \mid AS \mid S$ .
$S \to aB$ : $B$ nullable ⟹ add $S\to a$ . So $S \to aB \mid a$ .
$A \to B$ : $B$ nullable ⟹ would add $A\to\varepsilon$ — drop it (not $S_0$ ). Keep $A\to B$ .
$A \to S$ : keep (no nullable symbol).
$B \to b$ : keep. Delete $B\to\varepsilon$ .

After DEL: $S_0\to S$ ; $S \to ASA \mid SA \mid AS \mid S \mid aB \mid a$ ; $A \to B \mid S$ ; $B \to b$ .

UNIT. Find unit pairs (reflexive + transitive closure over unit rules $S\to S$ , $A\to B$ , $A\to S$ , $S_0\to S$ ):

$(S_0,S)$ , and via $S$ none further (S's only unit rule is $S\to S$ ). $S\to S$ is a trivial self-unit, removed.
$(A,S)$ , $(A,B)$ .

Now, for each variable, collect non-unit bodies of every variable it reaches:

Non-unit bodies of $S$ : $\{ASA, SA, AS, aB, a\}$ .
Non-unit bodies of $A$ : from $A\Rightarrow^* B$ gives $\{b\}$ ; from $A\Rightarrow^* S$ gives $\{ASA, SA, AS, aB, a\}$ .
Non-unit bodies of $B$ : $\{b\}$ .

Result (unit rules dropped):

\begin{aligned} S_0 &\to ASA \mid SA \mid AS \mid aB \mid a\\ S &\to ASA \mid SA \mid AS \mid aB \mid a\\ A &\to ASA \mid SA \mid AS \mid aB \mid a \mid b\\ B &\to b \end{aligned}

Why this step? Every rename is replaced by the actual productive bodies it could reach.

TERM. Terminal $a$ appears mixed in $aB$ : add $T_a\to a$ , rewrite $aB \to T_a B$ . (Standalone $\to a$ and $\to b$ stay.)

\begin{aligned} S_0,S &\to ASA \mid SA \mid AS \mid T_a B \mid a\\ A &\to ASA \mid SA \mid AS \mid T_a B \mid a \mid b\\ B &\to b,\quad T_a \to a \end{aligned}

BIN. Only $ASA$ (length 3) is too long. Add $A_1 \to SA$ , rewrite $ASA \to A\,A_1$ :

\begin{aligned} S_0,S &\to A A_1 \mid SA \mid AS \mid T_a B \mid a\\ A &\to A A_1 \mid SA \mid AS \mid T_a B \mid a \mid b\\ A_1 &\to SA,\quad B \to b,\quad T_a \to a \end{aligned}

Why this step? Now every rule is $A\to BC$ or $A\to a$ — CNF achieved. ✓

Worked Example 2 — small & clean

Grammar: $S \rightarrow aSb \mid ab$ . (No ε, no unit rules — DEL and UNIT do nothing.)

TERM: $T_a \to a$ , $T_b \to b$ . Rules: $S \to T_a S T_b \mid T_a T_b$ . Why? Isolate $a,b$ .

BIN: $S \to T_a S T_b$ (length 3): $S \to T_a X_1$ , $X_1 \to S T_b$ . Why? Cut length-3 into two length-2 rules.

Final CNF: $S \to T_a X_1 \mid T_a T_b,\quad X_1 \to S T_b,\quad T_a \to a,\quad T_b \to b.$ Language $= \{a^n b^n : n\ge 1\}$ , unchanged. ✓

Forecast-then-Verify

Common mistakes

Flashcards

What two production forms are allowed in CNF (ignoring start-ε)?

A \to BC

(two variables) and

A \to a

(one terminal).

Which single rule may legally produce ε in CNF?

Only the start symbol:

S_0 \to \varepsilon

, and only if ε is in the language.

What is Sipser's order of the 5 CNF conversion steps?

START, DEL, UNIT, TERM, BIN.

Why does DEL/UNIT come before TERM/BIN in Sipser?

ε- and unit-removal only shrink/rename RHSs, so doing them first means TERM/BIN never get undone.

Define a nullable variable.

A variable

A

with

A \Rightarrow^* \varepsilon

(derives the empty string).

In DEL, how do you patch

A\to XYZ

where

X,Z

are nullable?

Add a rule for every subset of

\{X,Z\}

omitted:

A\to XYZ\mid YZ\mid XY\mid Y

(never empty).

What is a unit production and how is it removed?

A rule

A\to B

(B a variable); remove by adding

A\to\gamma

for every non-unit body

\gamma

reachable as a unit pair

(A,B)

Why is CNF useful?

Parse trees become binary ⟹ enables CYK

O(n^3)

membership and the CFL pumping lemma.

In BIN, converting

A\to B_1B_2B_3

, what do you get?

A\to B_1 X_1

X_1\to B_2 B_3

(one fresh variable).

Why add a new start symbol

S_0

first?

So the start symbol never appears on any right-hand side, keeping later steps clean.

Recall Feynman: explain to a 12-year-old

Imagine LEGO instructions where each step can only do ONE of two things: snap two big blocks together, or place one single colored tile. No giant complicated steps allowed. CNF rewrites a messy building manual into this baby-simple style. The finished tower is exactly the same — but now a robot can follow the steps super fast and even check whether a given tower is buildable. We clean up by: giving a fresh "start" block, removing "build nothing" steps, removing lazy "call this block by another name" steps, then swapping loose colored tiles for named blocks, and finally chopping long steps into pairs.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, Chomsky Normal Form ka matlab hai grammar ko ek bilkul fixed "saaf-suthri" shape me laana. Isme har rule sirf do tarah ka ho sakta hai: ya toh ek variable se do variables ( $A \to BC$ ), ya ek variable se ek terminal ( $A \to a$ ). Bas. Mixed cheezein jaise $A\to aB$ , lambi rules $A\to BCD$ , khaali wali $A\to\varepsilon$ , aur rename wali $A\to B$ — sab ban hain (start symbol ka chhota exception chhod ke).

Faayda kya hai? Jab har rule do hisson me todta hai, toh parse tree ek binary tree ban jaata hai. Isse CYK algorithm se hum $O(n^3)$ me check kar sakte hain ki koi string language me hai ya nahi, aur CFL ka pumping lemma bhi clean prove hota hai. Isliye CNF ko grammar ka "assembly language" bolte hain.

Conversion ka Sipser order yaad rakhna zaruri hai: START, DEL, UNIT, TERM, BIN (mnemonic: "Some Dogs Understand Tricky Behaviour"). Pehle naya start symbol $S_0$ , phir nullable (khaali derive karne wale) variables hatao (DEL), phir unit/rename rules hatao (UNIT), phir terminals ko alag variable me daalo (TERM), aur aakhir me lambi rules ko do-do me chop karo (BIN). DEL aur UNIT pehle isliye, kyunki ye sirf RHS chhota ya rename karte hain — agar baad me kiya toh TERM/BIN ka kaam dobara karna pad jaata hai.

Ek important point DEL me: agar ek rule me kai nullable symbols hain, toh har subset ko drop karke alag-alag rule banao.

Chomsky Normal Form (CNF) — conversion