Chomsky Normal Form

A context-free grammar (CFG) is a tuple $G = (V, \Sigma, R, S)$ of variables, terminals, rules, and a start symbol, generating strings via leftmost or arbitrary derivations from $S$. In general, a rule's right-hand side (its body) can be any string over $V \cup \Sigma$, including the empty string. This flexibility is convenient for writing grammars but obstructs algorithms that want to reason inductively about "how a string of length $n$ was built." A grammar is in Chomsky Normal Form if every rule has one of these three shapes:

with the extra constraint that if $S \to \varepsilon$ is present, $S$ never appears on the right-hand side of any rule. Every body is either exactly two variables, exactly one terminal, or (only for the start symbol) empty. There are no productions like $A \to \varepsilon$ for non-start $A$, no productions like $A \to B$ (a "unit" or "chain" rule), and no productions like $A \to aBc$ or $A \to BCD$ with three or more symbols. The central theorem is an equivalence result: for every context-free language $L$, there is a CNF grammar $G'$ with $L(G') = L$. The proof is constructive — it is exactly the four-phase algorithm below — and each phase is independently justified by showing that derivations in the old grammar correspond to derivations in the new one and vice versa. This is the same proof pattern used when normalizing regular expressions, converting NFAs to DFAs, or reducing boolean circuits to normal forms: restrict the syntax while preserving the semantics (the generated language), so that downstream algorithms can assume a uniform shape without loss of generality. The technique of separating "start symbol" handling to isolate $\varepsilon$ generation echoes how derivations and parse trees cleanly track how substrings are assembled — CNF simply forces every internal parse-tree node to be strictly binary-branching (except leaves), which is what makes the tree structure countable and dynamic-programmable.

The conversion proceeds in a fixed order — reordering phases can silently reintroduce forbidden forms, so the sequence matters.

Phase 0 — New start symbol. Add a fresh start symbol $S_0$ with rule $S_0 \to S$, where $S$ was the old start symbol. This guarantees the start symbol never appears on the right-hand side of any rule, which is required so that later we can safely let $S_0 \to \varepsilon$ without corrupting other derivations.

Phase 1 — Eliminate ε-productions (nullable variables). A variable $A$ is nullable if $A \Rightarrow^* \varepsilon$. Compute the full set of nullable variables by fixed-point iteration, then remove every $\varepsilon$-rule (except possibly $S_0 \to \varepsilon$) while adding, for every rule whose body contains nullable variables, all versions of that rule with nullable occurrences deleted in every subset combination (excluding the case where the entire body would vanish, unless the head is $S_0$).

Phase 2 — Eliminate unit productions. A unit rule has the form $A \to B$ for variables $A, B$. Compute, for each variable $A$, the set of variables reachable via a chain of unit rules. Remove all unit rules, and for each $A$ that can reach $B$ via units, add every non-unit rule of $B$ directly as a rule for $A$.

Phase 3 — Break long and mixed bodies. Any rule with a terminal mixed into a body of length $\ge 2$, e.g. $A \to aB$, gets the terminal replaced by a fresh variable: $A \to U_a B$, $U_a \to a$. Any rule with three or more symbols, e.g. $A \to X_1 X_2 \cdots X_k$, is broken into a chain of fresh variables: $A \to X_1 Y_1$, $Y_1 \to X_2 Y_2$, …, $Y_{k-2} \to X_{k-1} X_k$. ``` CONVERT-TO-CNF(G = (V, Σ, R, S)): // Phase 0: fresh start symbol S0 := new symbol not in V R := R ∪ { S0 -> S } V := V ∪ { S0 } G.start := S0 // Phase 1: remove epsilon productions NULLABLE := {} repeat until no change: for each rule A -> body in R: if body == ε, or every symbol in body is in NULLABLE: add A to NULLABLE R' := {} for each rule A -> X1 X2 ... Xk in R (k >= 1): if A -> ε: continue // drop epsilon rules (handled separately) for each subset T of the positions i where Xi is in NULLABLE: body' := X1..Xk with positions in T deleted if body' is nonempty, OR A == S0: R'.add(A -> body') // (allow S0 -> ε to survive) R := R' with duplicates removed // Phase 2: remove unit productions for each variable A: UNIT-REACH(A) := smallest set containing A, closed under: if B in UNIT-REACH(A) and B -> C in R is a unit rule, then C in UNIT-REACH(A) R'' := { A -> body : A -> body in R and body is not a single variable } for each variable A: for each B in UNIT-REACH(A), B != A: for each rule B -> body in R that is NOT a unit rule: R''.add(A -> body) R := R'' with duplicates removed // Phase 3: binarize bodies R''' := {} TERM := {} // map terminal a -> variable U_a for each rule A -> X1 X2 ... Xk in R: if k == 1 and X1 is a terminal: R'''.add(A -> X1) // already CNF: A -> a else if k == 1 and X1 is a variable: // cannot happen: units already removed in Phase 2 else: // replace any terminal occurring inside a body of length >= 2 for i in 1..k: if Xi is a terminal a: if a not in TERM: TERM[a] := new variable U_a Xi := TERM[a] if k == 2: R'''.add(A -> X1 X2) else: // k >= 3, binarize with fresh variables Y1, ..., Y_{k-2} := new variables R'''.add(A -> X1 Y1) for i in 1..k-3: R'''.add(Yi -> X_{i+1} Y_{i+1}) R'''.add(Y_{k-2} -> X_{k-1} Xk) for each (a -> U_a) in TERM: R'''.add(U_a -> a) return G' = (V', Σ, R''', S0) ``` The order Phase 1 → Phase 2 → Phase 3 is not arbitrary. Removing ε-productions first can create new unit productions (e.g. $A \to BC$ with $C$ nullable becomes $A \to B$), so unit-elimination must come after. Eliminating unit productions can create bodies mixing terminals and variables of length $\ge 2$ that still need binarizing, so binarization must come last. Running Phase 3 before Phase 2 would leave unit rules unbroken; running Phase 2 before Phase 1 would miss unit rules generated by ε-removal.

Correctness. We must show $L(G') = L(G)$ (with the empty string handled by the $S_0 \to \varepsilon$ exception). The argument proceeds phase by phase, each showing that derivations biject (up to the specific rewriting) between the old and new rule sets. Phase 0 trivially preserves the language: $S_0 \Rightarrow S \Rightarrow^* w$ iff $S \Rightarrow^* w$, and since $S_0$ is fresh, it introduces no new derivations elsewhere. Phase 1 (ε-removal). Fix a derivation $A \Rightarrow^* w$ using the old rules. Whenever a nullable variable in some production body is used to derive $\varepsilon$, that occurrence contributes nothing to the final string, so the same derivation tree can be pruned: delete every subtree rooted at a nullable variable that yields $\varepsilon$, and the production at the parent becomes exactly one of the subset-deleted bodies added by the algorithm. Conversely, any derivation using a new subset-deleted rule can be "re-inflated" by reinserting an $\varepsilon$-derivation for each deleted position (using the original ε-productions), reproducing a valid old derivation of the same string. Thus $L(G_1) = L(G) \setminus \{\varepsilon\}$ if $\varepsilon \notin L(G)$-handling, or with $S_0 \to \varepsilon$ retained precisely to keep $\varepsilon$ in the language when $S \Rightarrow^* \varepsilon$ originally. Phase 2 (unit-removal). If $A \Rightarrow^* B \Rightarrow^*$ (via a chain of unit rules) $\Rightarrow$ body $\Rightarrow^* w$, then since unit-reachability is computed as the transitive closure of the unit-rule relation, $A$ directly gets a copy of $B$'s non-unit rule producing that same body, and hence the same derivation of $w$ collapses to one fewer step but produces the identical string. Conversely, every added rule $A \to \text{body}$ exists only because some genuine unit chain $A \to \cdots \to B$ existed and $B \to \text{body}$ was a real non-unit rule in the original grammar, so every new derivation corresponds to an old one. Phase 3 (binarization). Introducing fresh variables $U_a$ with $U_a \to a$ and chaining fresh $Y_i$ variables is a pure notational refactor: the derivation $A \Rightarrow X_1 X_2 \cdots X_k \Rightarrow^* w$ corresponds exactly to $A \Rightarrow X_1 Y_1 \Rightarrow X_1 X_2 Y_2 \Rightarrow \cdots \Rightarrow X_1 \cdots X_k \Rightarrow^* w$, a longer but string-preserving derivation, and this correspondence is clearly reversible (contract the chain of $Y_i$'s back into one step). None of these fresh variables appear anywhere else in the grammar, so no unintended new strings become derivable. Chaining these four language-preserving equivalences gives $L(G') = L(G)$, establishing the CNF equivalence theorem.

Termination. Each phase operates over a finite rule set and finite alphabet; nullable-set computation and unit-reachability computation are both monotone fixed-point iterations over a finite universe (bounded by $|V|$), so each terminates in at most $|V|$ rounds. Binarization processes each rule once, producing finitely many fresh variables. The whole algorithm halts.

Size and time complexity. Let $n = |R|$ (number of original rules) and let $m$ be the maximum body length. Phase 1's nullable-subset expansion is the potential blowup point: a rule with $k$ symbols, all nullable, generates up to $2^k - 1$ new rule variants (all subsets except deleting everything, unless the head is $S_0$). If body lengths are bounded by a constant (as is typical for grammars written by hand or produced by tools), this is a constant-factor blowup per rule, giving overall size $O(n \cdot 2^m)$ and hence polynomial in $n$ for fixed $m$; in the worst case with unbounded body length, this step is exponential in $m$. Phase 2 adds at most $O(|V|^2)$ new rules (one potential inlined rule per ordered pair of variables with a unit-chain relation, times the constant number of non-unit rules each variable owns). Phase 3 replaces each length-$k$ body with $O(k)$ new rules and $O(k)$ fresh variables, so it is linear in the total input size. In practice, for grammars with bounded-length productions (the overwhelmingly common case, including all grammars produced by standard tools and nearly all grammars written by hand), the entire conversion runs in time and produces an output grammar of size polynomial in the input size — commonly cited as $O(n^2)$ or better in rule count for reasonable inputs, though the theoretical worst case tied to the ε-elimination subset expansion is exponential in maximal body length. Being honest about this tradeoff matters: CNF conversion is "efficient" in the sense that matters for CYK's asymptotic parsing bound, but pathological grammars with very long, heavily nullable bodies can inflate grammar size substantially, which is a real practical concern in tools that auto-generate grammars.

Convert the following CFG (deliberately asymmetric — mixed terminals, a nullable variable, and a unit chain) to CNF.

with start symbol $S$.

After Phase 1, the rule set (before duplicate-removal cleanup) is:

Phase 2 (remove unit rules). Unit rules present: $S_0 \to S$, $S \to S$ (a self-loop unit rule — trivially removable, contributes nothing new), $A \to B$, $A \to S$. Unit-reachability: $S_0 \to S$; $A \to B$ and $A \to S$, and since $S$ reaches nothing further via units (its only unit-target is itself), $A$'s reachable set is $\{B, S\}$, and $S$'s (and hence $S_0$'s) reachable set is just itself (the self-loop $S \to S$ adds nothing). Inline non-unit rules of reachable targets:

• $S_0$ reaches $S$: copy $S$'s non-unit rules ($ASA, SA, AS, aB, a$) to $S_0$.
• $A$ reaches $B$: copy $B \to b$ to $A$.
• $A$ reaches $S$: copy $S$'s non-unit rules to $A$.

Result after Phase 2:

Phase 3 (binarize). Rules of length 1 ($S_0 \to a$, $A \to a$, $A \to b$, $B \to b$) are already CNF; keep them. Rules of length 2 with a terminal ($S_0 \to aB$, $S \to aB$, $A \to aB$) need the terminal replaced: introduce $U_a \to a$, giving $S_0 \to U_a B$, $S \to U_a B$, $A \to U_a B$. Rules of length 2 with two variables ($S_0 \to SA$, $S_0 \to AS$, $S \to SA$, $S \to AS$, $A \to SA$, $A \to AS$) are already CNF. Rules of length 3 ($S_0 \to ASA$, $S \to ASA$, $A \to ASA$) need one binarization step each: introduce fresh $Y \to SA$ shared across all three (since the suffix $SA$ recurs), giving $S_0 \to AY$, $S \to AY$, $A \to AY$, with $Y \to SA$.

Final CNF grammar:

Every rule is now `X → YZ` or `X → terminal`, exactly as required. Spot-check: the original string $ab$ should still be derivable. Original grammar: $S \to aB \to a\,b$ ✓. New grammar: $S_0 \to U_aB \to a\,b$ ✓ — same string, confirming the transformation preserved at least this instance of the language.

Noam Chomsky's 1956 and 1959 work on the mathematical structure of natural-language grammars sought a formal apparatus precise enough to reason about which string-generating rule systems could plausibly model human syntax. This effort produced the Chomsky hierarchy — regular, context-free, context-sensitive, and unrestricted (recursively enumerable) grammars — and, alongside it, the observation that context-free grammars could always be reshaped into a canonical binary-branching form without loss of generative power. This normal form, later named after him, became indispensable not for linguistics directly but for the algorithmic theory of parsing that followed, most directly the CYK algorithm developed independently around the same period.

The CYK algorithm, the canonical polynomial-time (cubic in string length) parser for arbitrary context-free grammars, is defined entirely in terms of a CNF grammar: its dynamic-programming table exploits the fact that every production splits a substring into exactly two independently parseable pieces, which is only guaranteed once the grammar is binarized. Any system that needs to parse an arbitrary context-free grammar without restricting to a deterministic subset — general-purpose natural-language parsers, ambiguity-checking tools, some bioinformatics pipelines modeling RNA secondary structure as context-free — runs a CNF conversion as a preprocessing step before invoking CYK or a close variant. CNF also underlies standard proofs in the theory itself: the pumping lemma for context-free languages is most cleanly proved by first placing the grammar in CNF (or Greibach Normal Form, a related canonical shape), because binary branching guarantees a bound on tree height relative to string length via the pigeonhole principle on repeated variables along a path — a bound that would be far messier to state for unrestricted-arity productions. Closure-property proofs (context-free languages closed under union, concatenation, Kleene star) are also frequently phrased using normalized grammars, since combining two CNF grammars cleanly is easier than combining two grammars with arbitrary rule shapes. Compiler theory courses and parser-generator tools that support general CFGs (as opposed to restricted LL/LR subsets) reference CNF or an equivalent binarized form when discussing worst-case parsing guarantees, and the equivalence between CFGs and pushdown automata is often first established for CNF-shaped grammars before generalizing, since the binary structure simplifies the stack-based construction.

Ask the tutor: Can you walk through why the CYK algorithm's correctness specifically depends on every CNF production having exactly two variables or one terminal?