Foundations — Chomsky Normal Form (CNF) — conversion

This page assumes you have seen none of the notation in the parent note. We build every symbol from the ground up, in the order you need them. Each block: plain words → the picture → why the topic needs it.

Before the symbols, here is the destination we are heading toward — the conditions a grammar must satisfy to be in CNF. Every definition below exists to make one of these precise. (A few terms below — terminal, variable, unit rule, start symbol — are defined properly in the numbered sections; here they are just previewed.)

---

1. Terminal — the actual letters of the string

Plain words. Think of the final output word, like aabb. Every character you can see in that word is a terminal. It is "terminal" because the building process terminates there — nothing more happens to it.

The picture. In Figure 1 (below), the letters at the very bottom (the leaves of the branching diagram) are terminals. They are the only things that survive into the printed string. (This diagram is a parse tree — formally defined in §9; for now just read it as "the picture of one string being built.")

Figure 1. A branching diagram (parse tree, §9) for the string aabb. The red bottom row are the terminals — the only symbols that survive into the printed word.

Why the topic needs it. A type-2 CNF rule is $A\to a$: "this name becomes exactly one terminal." Terminals are the only things that make it into the output, so every string ultimately comes from these one-letter rules. See Context-Free Grammars for where terminals first appear.

---

2. Variable (non-terminal) — a temporary placeholder name

Plain words. A variable is like a labelled box: "$A$ = whatever goes here, to be decided by a rule." It must eventually be replaced by terminals; it can never remain in the final string.

The picture. In Figure 1, the internal nodes (everything above the bottom row) are variables. They are placeholders that got expanded downward until only terminals remained.

Why the topic needs it. A type-1 CNF rule is $A\to BC$: "this name becomes exactly two other names." Variables are the branching machinery. The whole conversion is about reshaping how variables expand.

---

3. Production / rule — one legal replacement, written with $\to$

Plain words. A production is a permission slip: "wherever you see $A$, you are allowed to swap it out for $\gamma$." The left side is always a single variable; the right side (the body, $\gamma$) is any mix of variables and terminals.

Why $\to$ and not $=$? An equals sign would mean two things are the same. But $A$ is a name and $\gamma$ is what it turns into — a one-way action, done during building only. That directionality is the entire point, so we use an arrow.

Why the topic needs it. CNF is a rule about the shape of every production's right side. To restrict rules you must first name them: $A\to BC$ (type-1), $A\to a$ (type-2), $A\to aB$ (illegal — mixes a terminal with a variable), and so on.

---

4. Grammar — the whole machine, as a 4-tuple

Plain words. A grammar is just these four lists bundled together: which names exist ($V$), which letters exist ($\Sigma$), which swaps are allowed ($R$), and where you begin ($S$). Every symbol in this whole page belongs to one of these four slots.

Why the topic needs it. CNF is a statement about $R$ (the shapes of the rules) and about $S$ (only $S$ may vanish). Naming the container $(V,\Sigma ,R,S)$ lets us say precisely which part each conversion step touches: START edits $S$ and $V$; DEL, UNIT, TERM, BIN all rewrite $R$. See Context-Free Grammars.

---

5. The pipe $\mid$ — shorthand for "or"

Plain words. When one variable has several possible replacements, we stack them on one line separated by $\mid$ instead of rewriting A → each time. So $B\to b\mid \epsilon$ is just $B\to b$ together with $B\to \epsilon$.

---

6. Epsilon $\epsilon$ — the empty string

Plain words. Imagine an empty text box: you typed nothing. That "nothing" still counts as a valid string, and we give it the name $\epsilon$ so we can talk about it. A rule $A\to \epsilon$ is called an ==$\epsilon$-production== and says "$A$ may simply vanish."

The picture. In Figure 2 (below), an $\epsilon$-production is drawn as a node whose only child is a hollow red dot — it contributes no leaf to the final word.

Figure 2. The $\epsilon$-production $B\to \epsilon$: the variable $B$ expands to the hollow red $\epsilon$ node and adds no letter to the output. Sibling $C\to c$ still contributes its leaf.

Why the topic needs it. The no-$\epsilon$ condition of CNF forbids $A\to \epsilon$ for every variable except the start symbol. The whole DEL step (short for delete $\epsilon$-productions) exists to hunt down variables that can vanish (called nullable) and rewrite around them. Without understanding $\epsilon$, DEL is meaningless.

---

7. Start symbol — where every derivation begins

Plain words. $S$ is the root of every parse tree — the single box you begin with before any rule fires. A grammar's language is exactly the set of all terminal-strings you can reach from $S$.

Why the topic needs it. CNF's optional rule, $S\to \epsilon$, is allowed only for the start symbol. The START step (short for new start symbol) even invents a brand-new start symbol $S_0$ so the original $S$ can be tidied without special-casing it.

---

8. Unit (rename) production — a variable that just renames another

Plain words. $A\to B$ does no real work: no letter appears, the diagram does not branch. It only says "an $A$ can be re-labelled a $B$." A unit step is one single application of such a rule. A rule like $A\to a$ is not a unit production (its body is a terminal), and $A\to BC$ is not one (its body has two variables).

Why the topic needs it. The no-unit condition of CNF forbids every rename rule. The UNIT step (short for eliminate unit productions) walks all unit pairs and replaces each rename by the real bodies it could eventually reach, then deletes the renames.

---

9. Derivation and $\Rightarrow$, ${\Rightarrow }^{\ast }$ — building a string step by step

Plain words. A derivation is the sequence of swaps that turns $S$ into a finished word. Each single swap is one $\Rightarrow$; the whole chain, however long, is one ${\Rightarrow }^{\ast }$.

Why two different arrows?

• $\to$ names a rule you own (a fixed replacement you're allowed to use).
• $\Rightarrow$ names a single move you actually made using one of those rules.
• ${\Rightarrow }^{\ast }$ names many moves collapsed together — "reachable eventually." (The restricted cousin $\stackrel{u}{{\Rightarrow }^{\ast }}$ from §8 is the same idea but limited to rename moves.)

The picture. Figure 3 (below) is a derivation: reading top-to-bottom, each level is one $\Rightarrow$ step; the whole tree is the ${\Rightarrow }^{\ast }$ from root to leaves.

Figure 3. A CNF-shaped derivation. The red edges highlight one single $\Rightarrow$ step ($S\Rightarrow AB$); the whole top-to-bottom tree is the collapsed ${\Rightarrow }^{\ast }$.

Why the topic needs it. "$A$ is nullable" is defined as $A{\Rightarrow }^{\ast }\epsilon$ (A can eventually vanish). "Unit pair $(A,B)$" is defined as $A\stackrel{u}{{\Rightarrow }^{\ast }}B$ (§8). Both DEL and UNIT are stated entirely in this notation.

---

10. Parse tree — the picture of a derivation

Plain words. Same information as a derivation, but as a shape instead of a list. If a rule was $A\to BC$, node $A$ gets two children $B$ and $C$.

Why the topic needs it — the whole payoff. Look only at the variable nodes of a CNF parse tree (ignore the terminal leaves that hang off type-2 rules):

• a type-1 rule $A\to BC$ gives a variable node exactly 2 variable-children,
• a type-2 rule $A\to a$ gives a variable node exactly 1 terminal leaf and no further branching.

So the tree of variable nodes is a binary tree (each has two children or is a leaf-parent). Counting precisely, for a non-empty string of length $n$: there are exactly $n$ type-2 nodes (one variable per output letter) and exactly $n-1$ type-1 nodes (the branch points that join $n$ pieces into one), giving $2n-1$ variable nodes in total. If you also count the $n$ terminal leaves themselves, the grand total is $3n-1$ nodes. The key fact is that all these counts are fixed by $n$ alone — that predictability is what powers the CYK Algorithm ($O(n^3)$ membership) and the Pumping Lemma for CFLs.

---

11. Subset $\subseteq$ — the DEL patching notation

Plain words. If $P$ is a bag of positions, a subset $D$ is any handful you scoop out.

The picture. In Figure 4 (below), the body $XYZ$ has nullable positions $P=\{1,3\}$ (the $X$ and the $Z$ can vanish). Each red-boxed selection $D$ — drop nothing, drop $X$, drop $Z$, drop both — yields one new rule. Four subsets → four candidate rules (the "drop everything" one is discarded if it empties the body).

Figure 4. Subsets of the nullable positions $P=\{1,3\}$ of the body $XYZ$. Each red selection $D$ produces one patched rule.

Why the topic needs it. DEL cannot just add one rule per nullable symbol; it must try every subset of the nullable positions at once. The notation $D\subseteq P$ is exactly how the parent's "general patching rule" ranges over all these combinations — so understanding $\subseteq$ is what makes DEL correct rather than a common under-counting mistake.

---

12. The five pipeline steps: what START, DEL, UNIT, TERM, BIN each do

The parent conversion runs five named steps in order. Several were explained above; here are all five in one place so the mnemonic is not hollow.

---

Prerequisite map

How to read the map: the leaves at the top are the raw symbols (§1–§7); they assemble into a grammar, which supports derivations and their picture the parse tree; the unit-rule and epsilon strands feed the UNIT and DEL cleanup steps; all strands converge on the CNF conversion goal — the parent note.

---

Equipment checklist