Chomsky Normal Form

Context: FIT2014_MOC · the binary-tree normal form for a CFG ➔ the enabling hypothesis for both CYK and the CFL pumping lemma Parent Framework: Context-Free Grammars (CFG)

Quick Revision

• 🎯 Objective: rewrite any CFG so every rule is $A\to BC$ (live) or $A\to \mathtt{z}$ (dead) ➔ every parse tree becomes binary, which is what makes tree-height arguments and table parsing work.
• 📦 Core Components: live production ➔ exactly two nonterminals | dead production ➔ exactly one terminal. Nothing else is permitted.
• ⚡ Key Constraint: CNF generates the non-empty words only — $\epsilon$ is handled separately by the nullability algorithm.

📜 The theorem

Theorem. For any context-free language $L$, the non-empty words in $L$ can be generated by a grammar in Chomsky Normal Form.

• Why it matters ➔ two later results are stated for CNF grammars and inherit their generality from this theorem: the polynomial-time CYK Algorithm, and the Pumping Lemma for Context-Free Languages.
• ⚠ Name clash ➔ Chomsky Normal Form (grammars) vs Conjunctive Normal Form (propositional logic). Same acronym, unrelated objects — the exam exploits this.

📝 How It Works — the five-step conversion

1. Eliminate $\epsilon$-productions

For every rule $X\to \epsilon$: for every other rule with $X$ in the body, add all rules obtained by deleting some subset of the $X$ occurrences (keeping the original), then remove $X\to \epsilon$.

old rule with $X$ in body	new rules
$A\to \mathtt{b}XQ$	$A\to \mathtt{b}XQ$, $A\to \mathtt{b}Q$
$A\to \mathtt{b}XQX$	$A\to \mathtt{b}XQX$, $A\to \mathtt{b}QX$, $A\to \mathtt{b}XQ$, $A\to \mathtt{b}Q$
$A\to X$	$A\to X$, $A\to \epsilon$ (a new $\epsilon$-rule — repeat the step)

• Iterate to fixpoint ➔ the step creates new $\epsilon$-productions; stop only when none remain. Invariant achieved: no rule has an empty RHS.
• Housekeeping (optional, simplifying) ➔ a nonterminal that now never appears on the left of any rule can never be replaced, so every rule containing it on the right is dead code and may be deleted.

2. Eliminate unit productions

For every rule $X\to Y$ (nonterminal to single nonterminal): for every rule with $Y$ on the left, add the same rule with $X$ on the left (keeping the original), then remove $X\to Y$.

old rule with $Y$ on left	new rules
$Y\to \mathtt{ab}QR$	$Y\to \mathtt{ab}QR$, $X\to \mathtt{ab}QR$
$Y\to Q$	$Y\to Q$, $X\to Q$ (unless $X\to Q$ was already handled)
$Y\to X$	$Y\to X$, $X\to X$

• Invariant achieved ➔ every RHS is either a single terminal or at least two symbols.

3. Give each terminal its own nonterminal

For each terminal $\mathtt{z}$, create a fresh nonterminal $X_{\mathtt{z}}$ and the rule $X_{\mathtt{z}}\to \mathtt{z}$. (Terminals $\mathtt{a},\mathtt{b}$ ➔ $X_{\mathtt{a}}\to \mathtt{a}$, $X_{\mathtt{b}}\to \mathtt{b}$.)

4. Purge terminals from the long rules

In every rule that does not just produce a single terminal, replace each terminal by its new nonterminal: $Y\to \mathtt{ab}QR$ becomes $Y\to X_{\mathtt{a}}{X}_{\mathtt{b}}QR$.

• Invariant achieved ➔ every RHS is a single terminal or ≥2 nonterminals.

5. Break rules down to exactly two nonterminals

Chain fresh nonterminals until every long RHS is binary.

old rule	new rules
$Y\to Z_1{Z}_2{Z}_3$	$Y\to Z_{12}{Z}_3$, $Z_{12}\to Z_1{Z}_2$
$Y\to Z_1{Z}_2{Z}_3{Z}_4$	$Y\to Z_{12}{Z}_{34}$, $Z_{12}\to Z_1{Z}_2$, $Z_{34}\to Z_3{Z}_4$
$Y\to Z_1{Z}_2{Z}_3{Z}_4{Z}_5$	$Y\to Z_{1234}{Z}_5$, $Z_{1234}\to Z_{12}{Z}_{34}$, $Z_{12}\to Z_1{Z}_2$, $Z_{34}\to Z_3{Z}_4$

• Invariant achieved (final) ➔ every RHS is a single terminal or exactly two nonterminals. ∎

---

📊 Exam Execution Trace & Applied Exercises

Manual Execution Trace

No $\epsilon$- or unit productions here, so steps 1–2 are skipped.

Original	After steps 3 & 4	After step 5 (CNF)
$S\to \mathtt{b}A$	$S\to X_{\mathtt{b}}A$	$S\to X_{\mathtt{b}}A$
$S\to \mathtt{a}B$	$S\to X_{\mathtt{a}}B$	$S\to X_{\mathtt{a}}B$
$A\to \mathtt{a}$	$A\to \mathtt{a}$	$A\to \mathtt{a}$
$A\to \mathtt{a}S$	$A\to X_{\mathtt{a}}S$	$A\to X_{\mathtt{a}}S$
$A\to \mathtt{b}AA$	$A\to X_{\mathtt{b}}AA$	$A\to YA$, $Y\to X_{\mathtt{b}}A$
$B\to \mathtt{b}$	$B\to \mathtt{b}$	$B\to \mathtt{b}$
$B\to \mathtt{b}S$	$B\to X_{\mathtt{b}}S$	$B\to X_{\mathtt{b}}S$
$B\to \mathtt{a}BB$	$B\to X_{\mathtt{a}}BB$	$B\to ZB$, $Z\to X_{\mathtt{a}}B$
—	$X_{\mathtt{a}}\to \mathtt{a}$, $X_{\mathtt{b}}\to \mathtt{b}$	$X_{\mathtt{a}}\to \mathtt{a}$, $X_{\mathtt{b}}\to \mathtt{b}$

• Read step 5 carefully ➔ only the three-nonterminal rules changed; $A\to X_{\mathtt{a}}S$ was already binary and passed through untouched.

Applied Exercise

Problem: convert $S\to \mathtt{a}S\mathtt{a}\mid \mathtt{b}$ to CNF.

$$\begin{array}{rl}\text{Steps 3–4:}& S\to ASA,S\to \mathtt{b},A\to \mathtt{a}\\ \text{Step 5 (split }ASA):& S\to TA,T\to AS\end{array}$$

Final Extracted Output: $S\to TA\mid \mathtt{b}$, $T\to AS$, $A\to \mathtt{a}$. (This grammar is the input to the CYK Algorithm trace.)

---

🕳️ Nullability — the case CNF cannot cover

CNF covers $L\setminus \{\epsilon \}$, so decide $\epsilon \in L$ by a separate marking algorithm on the original grammar. A nonterminal $A$ is nullable iff $A\Rightarrow \cdots \Rightarrow \epsilon$.

1. For every rule $X\to \epsilon$, mark $X$ nullable.
2. While there is a rule $Y\to Y_1{Y}_2\cdots Y_k$ whose RHS is all nonterminals and all of them are marked: mark $Y$.
3. If the start symbol $S$ is marked, Accept ($\epsilon \in L$); else Reject.

• Why it terminates ➔ each pass marks at least one new nonterminal or none at all; there are finitely many, so it reaches a fixpoint.
• ⚠ Step 2’s precondition ➔ the RHS must contain no terminals. One terminal anywhere on the RHS makes that rule unusable for nullability.

⚠️ Common Mistakes

• 💡 Chomsky ≠ Conjunctive ➔ Conjunctive Normal Form is $\wedge$-of-$\vee$-clauses in logic; Chomsky NF is a grammar shape. Both abbreviate “CNF” in this unit.
• 💡 Deleting the original rule in steps 1–2 ➔ you keep $A\to \mathtt{b}XQ$ and add $A\to \mathtt{b}Q$; only the $X\to \epsilon$ (resp. $X\to Y$) rule itself is removed.
• 💡 Stopping after one pass ➔ both step 1 and step 2 can create the very thing they eliminate. Iterate to fixpoint.
• 💡 Claiming CNF generates $L$ ➔ it generates $L\setminus \{\epsilon \}$. If $\epsilon \in L$, say so and run nullability separately.
• 💡 Leaving a mixed RHS ➔ $A\to \mathtt{a}B$ is not CNF; only $A\to \mathtt{a}$ (dead) and $A\to BC$ (live) qualify.

🧠 Active Recall

What does the binary shape of CNF actually buy, and where is it used?

Answer

• Short answer: every parse tree becomes a binary tree, so $\#\text{leaves}\le 2^{\text{max path length}-1}$ — a bound linking word length to tree height, and hence to the number of nonterminals on a root-to-leaf path.
• Why: Two consumers ➔ the CFL pumping lemma uses that bound to force a repeated nonterminal on a path once $|w|>2^{k-1}$; the CYK Algorithm uses binary rules so each substring need only be split into two parts, giving a polynomial-time table fill.
• Bonus: the same shape kills $\epsilon$ and unit rules, so no derivation step can ever shrink or merely rename — which is what makes those bounds tight.

Step 1 removes $X\to \epsilon$ but must be repeated. Why can it not finish in one pass?

Answer

• Short answer: a rule whose RHS is exactly $X$, i.e. $A\to X$, spawns $A\to \epsilon$ — a brand new $\epsilon$-production — so the process must loop until no $\epsilon$-rule survives.
• Why: Nullability propagates upward ➔ the same fact drives the nullability algorithm: emptiness climbs the grammar from $\epsilon$-rules through all-nonterminal rules. Step 1 is that propagation, performed destructively.