Chomsky Normal Form (CNF) — conversion: Visual walkthrough

Step 0 — What are we even looking at?

WHAT. A grammar is a set of rewrite rules. On the left of every arrow sits a single variable (a placeholder, written as a capital letter). On the right sits a string of variables and terminals (the actual output letters, written lowercase). The special symbol $ε$ means "the empty string — nothing at all".

WHY. Before transforming anything, we must agree on the shapes. CNF is a promise about the right-hand side of every rule. So the whole game is: reshape every right-hand side until it is one of exactly two allowed pictures.

PICTURE. The two legal CNF shapes, drawn as tree fragments.

Figure — Chomsky Normal Form (CNF) — conversion

Our patient for this whole page: $S \to A S A ∣ a B, A \to B ∣ S, B \to b ∣ ε$

Read $∣$ as "or" — it just lists several rules with the same left side. Notice the mess: $A S A$ is too long (3 symbols), $a B$ mixes a terminal with a variable, $A \to B$ is a rename, and $B \to ε$ vanishes. Every disease CNF cures is present here.

Step 1 — START: give the start symbol a bodyguard

WHAT. Add one brand-new variable $S_{0}$ and one rule $S_{0} \to S$ . Now $S_{0}$ is the start symbol; the old $S$ becomes an ordinary worker.

WHY. CNF allows $ε$ only from the start symbol. Later we will erase $ε$ -rules everywhere else. If the start symbol also appeared inside other rules, erasing would tangle its two jobs (being the root, and being a building block). $S_{0}$ points only downward and appears on no right-hand side, so it stays clean forever.

PICTURE. The new root sits on top; nothing points back up into it.

Step 2 — DEL: find who can vanish, then erase $ε$

WHAT. First compute the nullable set $N$ — every variable that can eventually derive $ε$ . Then, for each rule, add copies with the nullable symbols dropped, and finally delete the bare $\to ε$ rules.

WHY. A rule like $B \to ε$ is illegal in CNF (for non-start $B$ ). But we cannot just delete it — some strings depend on $B$ disappearing. So we pre-bake every "what if this vanished?" outcome directly into the other rules, then throw the $ε$ -rule away safely.

PICTURE — building $N$ by fixed point. We keep adding variables until nothing new appears.

Reading the picture:

$B \to ε$ directly, so $vanishes on its own B \in N$ .
$A \to B$ , and every symbol on that right side ( $B$ ) is now in $N$ , so $vanishes because B does A \in N$ .
Check the rest: no other rule has an entirely nullable right side. $N$ stops growing. $N = {A, B}$

PICTURE — patching $S \to A S A$ . Both $A$ 's are nullable, so we drop the left one, the right one, or both.

Term by term for $S \to pos 1, nullable A pos 2, not S pos 3, nullable A$ :

drop neither → $A S A$
drop pos 3 → $A S$
drop pos 1 → $S A$
drop both → $S$

So $S \to A S A ∣ A S ∣ S A ∣ S$ . For $S \to a B$ ( $B$ nullable): drop $B$ → add $S \to a$ . For $A \to B$ ( $B$ nullable): dropping $B$ would leave empty, i.e. $A \to ε$ — forbidden, so we discard that copy and keep $A \to B$ . Finally delete $B \to ε$ .

Step 3 — UNIT: erase the renames

WHAT. A unit rule is $A \to B$ — one variable renamed to another, producing no letter and no branch. We find every unit pair $(A, B)$ meaning " $A$ can reach $B$ using only renames", then copy $B$ 's real (non-unit) rules onto $A$ , and delete all renames.

WHY. Renames add tree depth but no information — they cannot be a "two variables" node or a "one terminal" node, so they are illegal in CNF. The fix is to short-circuit them: wherever a rename could eventually reach a productive body, attach that body directly.

PICTURE. Following the rename arrows, then collapsing them into direct edges.

The unit pairs here (a variable always reaches itself, plus follow the arrows):

$(S_{0}, S)$ : so $S_{0}$ inherits $S$ 's real bodies.
$S \to S$ is a trivial self-rename — just delete it.
$A \to B$ and $A \to S$ : so $A$ inherits both $B$ 's and $S$ 's real bodies.

Collect each variable's non-unit bodies:

real bodies of $S$ : ${A S A, A S, S A, a B, a}$
real bodies of $A$ : from reaching $B$ → ${b}$ ; from reaching $S$ → ${A S A, A S, S A, a B, a}$

Step 4 — TERM: pull terminals out of long rules

WHAT. Wherever a terminal sits next to other symbols (like $a$ in $a B$ ), invent a variable $T_{a}$ with the single rule $T_{a} \to a$ , and swap the loose $a$ for $T_{a}$ .

WHY. CNF forbids mixing — a two-child node must be two variables, never a letter beside a variable. A lone $A \to a$ is already legal, so we only touch terminals that share a right-hand side with something else.

PICTURE. The terminal $a$ is lifted out into its own tiny rule.

Only $a B$ mixes. Introduce $new variable T_{a} \to the isolated letter a$ , and rewrite $a B \to T_{a} B$ (now two variables). The standalone $\to a$ and $\to b$ stay untouched.

Step 5 — BIN: chop everything down to pairs

WHAT. Any right-hand side longer than 2 gets cut into a chain of length-2 rules, each new link stored in a fresh helper variable.

WHY. The last illegal shape is too long: $A S A$ has three symbols. A binary tree node holds exactly two children, so we split "first symbol, then the rest", and let a helper variable be "the rest".

PICTURE. $A S A$ becomes a two-level fold: $A$ paired with a helper that unfolds into $S A$ .

For $S \to keep first A pack into helper A_{1} S A$ : create $A_{1} \to S A$ and rewrite $A S A \to A A_{1}$ . Every other rule is already length $\leq 2$ .

Edge cases you must be able to survive

The one-picture summary

The whole pipeline in one strip: a messy right-hand side enters on the left and leaves on the right as pure "two boxes" and "one letter" pieces. Read the amber arrows in order — START, DEL, UNIT, TERM, BIN — the same order Sipser insists on, because DEL and UNIT can only shrink rules, so running them first means TERM and BIN never have to be redone.

Recall Feynman retelling — say it like a story

We had a grammar full of bad habits. First we hired a bodyguard $S_{0}$ so the real start symbol could be handled without breaking anything. Then we hunted down every variable that could vanish into nothing and, before deleting those vanishing rules, we pre-wrote every "what if it's gone?" version into the surviving rules. Next we spotted lazy renames — a variable that just points at another — and we replaced each one with the actual work the target does. Then we found terminals hiding among variables and gave each its own little factory $T_{a} \to a$ . Finally we took every rule that was too long and folded it into a chain of pairs using helper variables. At the end, every rule is either "combine two things" or "emit one letter" — a perfect binary tree grammar that CYK can parse in $O (n^{3})$ .

Recall Self-test

Why must DEL run before TERM/BIN? ::: DEL/UNIT can only shrink or rename right-hand sides; doing them first means the freshly created TERM/BIN variables never need re-cleaning. In $A \to X Y Z$ with $X, Z$ nullable, what does DEL produce? ::: $A \to X Y Z ∣ Y Z ∣ X Y ∣ Y$ — every subset dropped except the empty one. After the full conversion, what is $A_{1}$ 's only rule? ::: $A_{1} \to S A$ .

Related: Context-Free Grammars · CYK Algorithm · Pumping Lemma for CFLs · Greibach Normal Form · Pushdown Automata