Worked examples — Chomsky Normal Form (CNF) — conversion

Before we start, one reminder of the vocabulary every example uses. A terminal is an actual output letter (lowercase, like $a,b$). A variable (or non-terminal, uppercase like $S,A$) is a placeholder that gets rewritten. A production $A\to \gamma$ is a rewrite rule: "wherever you see $A$, you may replace it with $\gamma$." $\epsilon$ means the empty string — nothing at all. These come from Context-Free Grammars; we build every step from them.

---

The scenario matrix

#	Cell (case class)	What makes it tricky	Hit by
C1	Already clean, only TERM+BIN needed	no ε, no unit — most students over-work it	Ex 1
C2	Multiple nullable positions in one rule	must add every subset, not one rule	Ex 2
C3	Chained nullables (A nullable because B is)	fixed-point iteration, order matters	Ex 3
C4	Unit-rule chain 3 deep ($A\to B\to C$)	transitive closure of renames	Ex 4
C5	Start symbol on a right-hand side + ε in language	why START step exists; $S_0\to \epsilon$ survives	Ex 5
C6	Long RHS of pure terminals ($A\to abcd$)	TERM then BIN cascade, many helpers	Ex 6
C7	Useless / degenerate: rule that only self-loops	$S\to S$ vanishes, empty language edge	Ex 7
C8	Real-world word problem	translate an English spec into a grammar, then CNF	Ex 8
C9	Exam twist: everything at once + count the rules	combine C2, C4, C6 and predict final size	Ex 9

Every worked example below is tagged with the cell it fills. Together they cover the whole table.

---

Ex 1 — the "already clean" trap · cell C1

Forecast: DEL and UNIT — do they do anything here? How many new variables does TERM create? Guess the final rule count before reading on.

1. START. Add $S_0\to S$. Why this step? CNF permits the start symbol to go to $\epsilon$; keeping the start off every right-hand side means later steps can never tangle it. Here $S$ never appears on a right side anyway, but we follow the pipeline honestly.
2. DEL. Nullable set: no rule has $\epsilon$, so $N=\varnothing$. Nothing to patch. Why this step? Without a nullable variable there is no illegal $A\to \epsilon$ to remove — DEL is a no-op. Recognising this saves you from imaginary work.
3. UNIT. Unit rules are $A\to B$ (one variable to one variable). We have $S_0\to S$. Its only source of non-unit bodies is $S$: those are $\{aS,b\}$. Replace: $S_0\to aS\mid b$; drop $S_0\to S$. Why this step? A rename produces no letter and no branching, so we substitute the actual bodies it eventually reaches.
4. TERM. Terminal $a$ is mixed with a variable in $aS$. Add $T_a\to a$, rewrite $aS\to T_{a}S$. Standalone $\to b$ is already legal. Why this step? CNF forbids mixing a terminal and a variable in the same body.
5. BIN. Longest body now is $T_{a}S$ (length 2). Nothing to chop.

Final CNF: $S_0\to T_{a}S\mid b,S\to T_{a}S\mid b,T_a\to a.$

Verify: Derive $aab$: $S\Rightarrow T_{a}S\Rightarrow aS\Rightarrow a{T}_{a}S\Rightarrow aaS\Rightarrow aab$. Every step used $A\to BC$ or $A\to a$. Language is $\{a^{n}b:n\ge 0\}$, unchanged. Rule count = 5. ✓

---

Ex 2 — several nullables in one rule · cell C2

Forecast: Which of $X,Y,Z$ are nullable? The rule $S\to XYZ$ will spawn how many patched versions? (Careful — it is not three.)

1. START. Add $S_0\to S$. Why this step? Standard hygiene for the start symbol — keep it off every right-hand side so ε handling never tangles.
2. DEL — find nullables. $X\to \epsilon$ so $X\in N$; $Z\to \epsilon$ so $Z\in N$; $Y$ has no $\epsilon$-path so $Y\notin N$. Thus $N=\{X,Z\}$. Why this step? We must know which positions can disappear before patching.
3. DEL — patch $S\to XYZ$. Nullable positions are $\{1,3\}$ (the $X$ and the $Z$). For every subset of those to drop:
   • drop nothing: $XYZ$
   • drop $X$: $YZ$
   • drop $Z$: $XY$
   • drop both: $Y$ $S\to XYZ\mid YZ\mid XY\mid Y.$ Also delete $X\to \epsilon$ and $Z\to \epsilon$ (neither is $S_0$). Why this step? Each nullable symbol either stays or vanishes independently, so we cover all $2^2=4$ combinations. We never delete down to empty here because $Y$ always remains.
4. UNIT. $S_0\to S$ and $S\to Y$ are the unit rules. Replace $S_0\to S$ by $S$'s bodies $\{XYZ,YZ,XY,Y\}$; but $S\to Y$ is itself a unit — resolve it to $Y$'s non-unit body $\{y\}$. So $S$ (and $S_0$) gain $y$ and lose $\to Y$. Why this step? Renames get flattened into the real bodies they eventually reach.
5. TERM. Standalone $\to x,\to y,\to z$ are already legal. No mixed rule exists. Why this step? TERM only fires when a terminal shares a body with another symbol; here every terminal already sits alone.
6. BIN. $XYZ$ has length 3: add $R_1\to YZ$, rewrite $XYZ\to X{R}_1$. All others length $\le 2$. Why this step? Only length-$>2$ bodies violate the binary shape; $XYZ$ is the sole offender.

Final CNF: $S_0,S\to X{R}_1\mid YZ\mid XY\mid y,R_1\to YZ,X\to x,Y\to y,Z\to z.$

Verify: The original language of $S$ is $\{[x]y[z]\}$ = the 4 strings $\{xyz,yz,xy,y\}$. Our final grammar can produce exactly these four terminal strings and no others. Count of patched versions of the long rule = 4. ✓

---

Ex 3 — chained nullables (fixed point) · cell C3

Forecast: Is $A$ nullable even though $A$ never has an $\epsilon$ rule directly? Trace the fixed-point iteration.

The figure below is a round-by-round film of the nullable set $N$ growing. Read it left to right: each boxed panel is one iteration, the arrow means "carry what you learned into the next round," and the coloured text names which rule let a new variable join $N$. It makes visible the one idea students miss — that $A$ enters $N$ only after $C$ is already inside, i.e. nullability spreads outward like a stain.

1. DEL — fixed-point iteration. Follow the panels in the figure: we grow $N$ in rounds.
   • Round 0 (leftmost panel): $N=\varnothing$.
   • Round 1 (blue panel): $C\to \epsilon$ ⟹ add $C$. $N=\{C\}$.
   • Round 2 (pink panel): $A\to C$ and $C\in N$ (the whole RHS is nullable) ⟹ add $A$. $N=\{C,A\}$.
   • Round 3 (yellow panel): $S\to AB$; is $B$ nullable? No. So $S$ not added. $N$ stops growing. Final $N=\{A,C\}$. Why this step? Nullability is transitive: a variable is nullable if it can reach $\epsilon$ through other nullable variables, not only by a direct $\to \epsilon$. The iteration keeps adding until nothing new appears — that "stops changing" point (the last panel) is the fixed point.
2. DEL — patch. In $S\to AB$, position 1 ($A$) is nullable, position 2 ($B$) is not. Subsets of $\{1\}$: keep $A$ → $AB$; drop $A$ → $B$. So $S\to AB\mid B$. Delete $C\to \epsilon$. Why this step? $A$ can vanish, so $S$ must be able to skip it.
3. UNIT. After DEL the unit rules are $A\to C$ and $S\to B$ (from the new $S\to B$). $C$ now has no productions (its only rule was $\epsilon$, deleted) — so $A\to C$ contributes nothing and $A$ becomes useless; drop it. $S\to B$ resolves to $B$'s body $b$: add $S\to b$. Why this step? A rename to a variable with an empty body dies; a rename to a real body is flattened.
4. TERM / BIN. $S\to AB$ is two variables (legal), $S\to b$ and $B\to b$ are single terminals (legal). Nothing to do. Why this step? No terminal is mixed into a longer body and no body exceeds length 2, so both passes are no-ops.

Final CNF: $S\to AB\mid b,A\to \text{(none — pruned)},B\to b.$ Since $A$ has no productions, $S\to AB$ can never terminate and is itself pruned, leaving $S\to b$.

Verify: Original language: $A\Rightarrow C\Rightarrow \epsilon$, so $S\Rightarrow AB\Rightarrow B\Rightarrow b$; also $S\Rightarrow AB$ with $A$ nonterminating gives nothing. Language $=\{b\}$. Final grammar $S\to b$ gives $\{b\}$. ✓

---

Ex 4 — a unit chain three deep · cell C4

Forecast: What is the set of unit pairs reachable from $S$? Which non-unit bodies does $S$ inherit?

1. START. Add $S_0\to S$. Why this step? Keep the start symbol off every right-hand side so the later ε/unit passes never have to special-case it.
2. DEL. No $\epsilon$ anywhere, $N=\varnothing$. No-op. Why this step? With no nullable variable there is no illegal $A\to \epsilon$ to remove.
3. UNIT — build the transitive closure. A unit pair $(X,Y)$ means $X{\Rightarrow }^{\ast }Y$ using only single-variable renames. Chain: $S\to A\to B\to C$. So the pairs are $(S,A),(S,B),(S,C),(A,B),(A,C),(B,C),$ plus $(S_0,S)$ and hence $(S_0,A),(S_0,B),(S_0,C)$ by transitivity. Why this step? A rename can hop through several variables; we must follow the chain all the way to the non-unit bodies at the end (here only $C$'s bodies $\{c,CC\}$).
4. UNIT — substitute. The only non-unit bodies live at $C$: $\{c,CC\}$. Every variable that reaches $C$ inherits them: $S_0,S,A,B,C\to c\mid CC.$ Drop all unit rules. Why this step? Once a rename's endpoint is found, we replace the rename by the actual productive bodies so no empty-branching rule survives.
5. TERM. $\to c$ is fine. No mixed terminal. Why this step? TERM only fires on a terminal sharing a body with another symbol; the lone $\to c$ is already legal.
6. BIN. $CC$ is length 2 — already binary. Why this step? Only length-$>2$ bodies need chopping, and none exist here.

Final CNF: $S_0,S,A,B,C\to CC\mid c.$

Verify: Original language: $C$ generates any nonempty binary tree of $c$'s = $\{c^n:n\ge 1\}$; $S$ renames down to $C$ so same language. Final grammar: $S_0\to CC$ / $c$ gives exactly $\{c^n:n\ge 1\}$. Unit pairs from $S_0$: $\{S_0,S,A,B,C\}$, size 5. ✓

---

Ex 5 — start on RHS + ε in language · cell C5

Forecast: $S$ appears on its own right side and $\epsilon$ is in the language. Does the final grammar keep an $\epsilon$-rule? On which symbol?

1. START. Add $S_0\to S$. Now $S_0$ is the only start, and $S$ still occurs in $S\to SS$. Why this step? This is exactly the case START exists for. If we deleted $S$'s $\epsilon$-rule while $S$ sits on a right-hand side, we would lose the ability to place $\epsilon$ at the top of the parse. The fresh $S_0$ absorbs the "may be empty" role.
2. DEL. $S\to \epsilon$ ⟹ $S\in N$. Then $S\to SS$ with both positions nullable ⟹ $S$ already in $N$. And $S_0\to S$ with $S$ nullable ⟹ $S_0\in N$. So $N=\{S,S_0\}$.
   • Patch $S\to SS$: nullable positions $\{1,2\}$; subsets give $SS,S,S,\varnothing$. We keep $SS$ and $S$ but must not create the empty RHS. So $S\to SS\mid S$.
   • Patch $S_0\to S$: drop-or-keep $S$ gives $S_0\to S$ and $S_0\to \epsilon$. Because $S_0$ is the start and $\epsilon \in L$, we keep $S_0\to \epsilon$.
   • Delete non-start $S\to \epsilon$. Why this step? CNF allows $S_0\to \epsilon$ as the single legal empty rule; that is how "$\epsilon$ is in the language" is recorded.
3. UNIT. Unit rules now: $S_0\to S$ and $S\to S$. The self-loop $S\to S$ is trivial — remove it (it adds nothing). $S$'s non-unit bodies: $\{SS\}$. So $S_0$ inherits $SS$: $S_0\to SS$. Drop unit rules. $S$ keeps $S\to SS$. Why this step? A variable renaming itself is pure noise; a rename to a real body is flattened.
4. TERM / BIN. $SS$ is binary and variable-only; legal. $S_0\to \epsilon$ is the permitted start ε-rule. Why this step? No terminal to isolate and no over-long body, so both passes are no-ops.

Final CNF: $S_0\to SS\mid \epsilon ,S\to SS.$

Verify: Original language: $S\to SS\mid \epsilon$ generates only $\epsilon$ (every $S$ must eventually vanish, no terminal exists). So $L=\{\epsilon \}$. Final grammar: $S_0\to \epsilon$ gives $\epsilon$; $S_0\to SS$ needs $S$ to produce a terminal, but $S\to SS$ never emits a terminal, so it is a dead branch → $L=\{\epsilon \}$. Matches. The one legal ε-rule lives on $S_0$. ✓

---

Ex 6 — long run of pure terminals · cell C6

Forecast: How many terminal-helper variables $T_x$? How many BIN helpers? Total rules?

The figure below shows the whole TERM-then-BIN cascade at a glance. The top row displays the offending length-4 body $S\to T_a{T}_b{T}_c{T}_d$ after terminals are isolated; the three stacked boxes below are the binary rules BIN carves out, and the downward arrows trace how each fresh helper ($X_1$, then $X_2$) swallows "the rest of the chain." Watching the arrows makes the count $k-2=2$ helpers obvious rather than memorised.

1. START / DEL / UNIT. No start-on-RHS, no ε, no unit rules — all no-ops. Why this step? None of these three passes has anything to fire on: the grammar has one rule with no variables, no $\epsilon$, and no rename.
2. TERM. Every terminal in a body of length $>1$ must be replaced by a variable. Add $T_a\to a,T_b\to b,T_c\to c,T_d\to d$ and rewrite: $S\to T_a{T}_b{T}_c{T}_d.$ Why this step? CNF forbids a raw terminal inside a multi-symbol body; four terminals ⟹ four helpers (top row of the figure).
3. BIN. Now $S\to T_a{T}_b{T}_c{T}_d$ has length 4. Chop left-to-right (the stacked boxes in the figure), each helper holding "the rest of the chain": $S\to T_a{X}_1,X_1\to T_b{X}_2,X_2\to T_c{T}_d.$ Why this step? Every internal parse node must have exactly two children; a length-$k$ body needs $k-2$ helpers. Here $k=4$ ⟹ 2 helpers ($X_1,X_2$).

Final CNF: $S\to T_a{X}_1,X_1\to T_b{X}_2,X_2\to T_c{T}_d,T_a\to a,T_b\to b,T_c\to c,T_d\to d.$

Verify: Terminal helpers = 4, BIN helpers = $k-2=2$, plus the original $S$-chain rule count. Language $=\{abcd\}$, unchanged: derive $S\Rightarrow T_a{X}_1\Rightarrow a{X}_1\Rightarrow a{T}_b{X}_2\Rightarrow ab{X}_2\Rightarrow ab{T}_c{T}_d\Rightarrow abc{T}_d\Rightarrow abcd$. ✓

---

Ex 7 — degenerate self-loop / empty language · cell C7

Forecast: What terminal strings can $S$ produce? What does CNF conversion leave you with?

1. START. $S_0\to S$; $S\to SS$. Why this step? Keep the start symbol off every right-hand side, following the pipeline honestly even on a degenerate grammar.
2. DEL. No ε ⟹ $N=\varnothing$. Why this step? No nullable variable exists, so there is no illegal $A\to \epsilon$ to remove.
3. UNIT. $S_0\to S$ is a rename; $S$'s non-unit body is $\{SS\}$, so $S_0\to SS$. $S\to SS$ stays. No self-unit ($SS$ is length 2, not a unit). Why this step? Flatten the rename $S_0\to S$ into the actual body it reaches.
4. TERM / BIN. $SS$ already binary and variable-only. Why this step? No terminal to isolate and no body longer than 2, so both passes do nothing.

Final "CNF": $S_0\to SS,S\to SS$.

But look closer: neither $S_0$ nor $S$ can ever reach a terminal — no production ever emits a letter. So the language is empty, $L=\varnothing$. Why this matters: CNF conversion does not invent terminals. A grammar with no terminal-producing rule stays terminal-free, and its language is empty. A clean-up pass (removing non-generating variables) would delete both rules, leaving a grammar with no productions at all — the honest CNF for the empty language is simply an empty rule set. This is the degenerate edge case CNF still handles correctly: it never fabricates a string that the original grammar could not produce.

Verify: Every derivation from $S$ only ever produces longer strings of $S$'s and never terminates in a terminal string. So $L=\varnothing$. ✓

---

Ex 8 — real-world word problem · cell C8

Forecast: "One or more letters" means recursion. Will TERM produce three helpers or fewer? Predict.

1. Grammar from the spec. "$l$, then $\ge 1$ copies of $x$, then $r$": $S\to lWr,W\to xW\mid x.$ $W$ = "one or more $x$'s." $S$ wraps it in brackets. Why this step? $\ge 1$ repetition is exactly right-recursion $W\to xW\mid x$; the outer rule bolts on the brackets.
2. START / DEL / UNIT. No start-on-RHS, no ε, no unit rules — no-ops. Why this step? $S$ never appears on a right side, no rule derives $\epsilon$, and no rule is a bare variable-to-variable rename, so all three passes are empty.
3. TERM. Terminals inside long bodies: $l,r,x$. Add $T_l\to l,T_r\to r,T_x\to x$. Rewrite: $S\to T_{l}W{T}_r,W\to T_{x}W\mid x.$ Why this step? $W\to x$ (length 1) stays raw; but the $x$ inside $xW$ must become $T_x$. So 3 helpers.
4. BIN. $S\to T_{l}W{T}_r$ has length 3: $S\to T_{l}Y,Y\to W{T}_r$. Everything else length $\le 2$. Why this step? The length-3 body $T_{l}W{T}_r$ is the only one violating the binary shape; one helper $Y$ fixes it.

Final CNF: $S\to T_{l}Y,Y\to W{T}_r,W\to T_{x}W\mid x,T_l\to l,T_r\to r,T_x\to x.$

Verify: Sanity-check <xx> = $lxxr$: $S\Rightarrow T_{l}Y\Rightarrow lY\Rightarrow lW{T}_r\Rightarrow l(T_{x}W)T_r\Rightarrow lxW{T}_r\Rightarrow lxx{T}_r\Rightarrow lxxr$. Length-4 string, binary tree has $2\cdot 4-1=7$ nodes. Helper count = 3 (TERM) + 1 (BIN) = 4. ✓

---

Ex 9 — exam twist: everything at once, count the rules · cell C9

Forecast: $A$ is nullable; $B\to B$ is a self-loop; $aA$ mixes a terminal. Predict how many rules survive on the right of it all.

1. START. $S_0\to S$. Why this step? Keep the start symbol off every right-hand side before the ε and unit passes run.
2. DEL. $A\to \epsilon$ ⟹ $A\in N$. No other ε. $N=\{A\}$.
   • $S\to AB$: position 1 nullable ⟹ add $S\to B$. So $S\to AB\mid B\mid a$.
   • $A\to aA$: position 2 ($A$) nullable ⟹ add $A\to a$. So $A\to aA\mid a$ (delete $A\to \epsilon$).
   • $B\to bB$: no nullable. $B\to B$ stays for now. Why this step? Only $A$ can vanish, so only $A$-positions branch; the illegal $A\to \epsilon$ is then removed.
3. UNIT. Unit rules: $S_0\to S$, $S\to B$, $B\to B$ (self-loop, drop it).
   • $B$'s non-unit bodies: $\{bB\}$ — but $B\to bB$ only, with no base case, so $B$ is non-generating (like Ex 7). Prune $B$.
   • With $B$ pruned, $S\to AB$ and $S\to B$ die. $S\to a$ survives.
   • $S_0\to S$ ⟹ $S_0\to a$. Why this step? A variable with no path to a terminal string is useless; removing it kills every rule that depends on it, and renames to survivors are flattened.
4. TERM. In $A\to aA$, terminal $a$ is mixed: $T_a\to a$, $A\to T_{a}A$. Standalone $A\to a$, $S\to a$, $S_0\to a$ stay. Why this step? CNF forbids the terminal $a$ sharing the body with variable $A$.
5. BIN. All bodies length $\le 2$. Nothing to chop. Why this step? No surviving body exceeds length 2, so the binary shape already holds.

Final CNF: $S_0\to a,S\to a,A\to T_{a}A\mid a,T_a\to a.$ (Note $A$ is now unreachable from $S_0$ too, so a reachability clean-up leaves just $S_0\to a$. We list the full set to show the mechanics.)

Verify: Original language: $B\to bB$ with no base ⟹ $B$ generates nothing ⟹ $S\to AB$ dead; only $S\to a$ works ⟹ $L=\{a\}$. Final grammar reachable from $S_0$: $S_0\to a$ ⟹ $L=\{a\}$. Matches. ✓

---

Recall Self-test

Nullable means a variable can derive what? ::: The empty string $\epsilon$ (possibly through other nullable variables). In DEL, a rule with $k$ nullable positions spawns how many patched versions (before removing the empty one)? ::: $2^k$ subsets, minus the all-dropped empty RHS when it occurs. Why does START exist? ::: So the start symbol never sits on a right-hand side, letting $S_0\to \epsilon$ be the single legal ε-rule (see Ex 5). A length-$k$ body needs how many BIN helper variables? ::: $k-2$. A variable that can never reach a terminal string is called? ::: Non-generating (useless) — prune it (see Ex 7, Ex 9).

See also: CYK Algorithm (why we wanted binary trees), Pumping Lemma for CFLs, Greibach Normal Form (a different normal form), Pushdown Automata, and the parent Chomsky Normal Form (CNF) — conversion.