JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Chomsky Normal Form

Cut every rule down to one of two shapes — a variable splitting into exactly two variables, or a variable producing one terminal — and a tangled grammar turns into a tidy machine of binary parse trees. That tidiness is exactly what makes the CYK parser and the context-free pumping lemma work.

One grammar, two rule shapes, no exceptions

By the previous guide you have learned to scrub a context-free grammar clean — strip out useless symbols, remove epsilon-productions, and remove unit productions, all in the right order. Cleaning leaves the rules legal but still ragged: one rule might be A → b C D e, another A → x, another A → B. Chomsky normal form (CNF) is the next, stricter step. It demands that EVERY production fit one of just two rigid shapes, with no leftovers.

The two allowed shapes are: (1) A → B C, a variable splitting into EXACTLY two variables (never a terminal, never one, never three); and (2) A → a, a variable producing EXACTLY one terminal. There is one tightly controlled exception: if the empty string epsilon belongs to the language, the single rule S → ε is permitted for the start symbol S — and S is then forbidden from appearing on any right-hand side, so that escape hatch can never leak into the rest of the grammar. That is the whole definition. No mixed rules like A → b C, no long rules, no unit rules A → B, no stray epsilons anywhere else.

Why bother? Because every parse tree becomes binary

The payoff is geometric. Recall from the parse-tree guide that the children of an internal node spell out a rule's right-hand side. In CNF every internal rule is A → B C, so every internal node has exactly TWO children that are themselves internal nodes; and every rule A → a makes a node with exactly one child, a leaf terminal. The result: every parse tree is a strict binary tree in its branching part, with the actual letters dangling as leaves at the bottom. No node fans out into three or five or seven children — it is always a clean two-way split.

This binary shape pins down the size of a tree precisely, and that precision is gold for proofs. A derivation of a string of length n (with n at least 1) in a CNF grammar takes exactly 2n - 1 steps: n - 1 applications of binary rules A → B C to build the branching, plus n applications of A → a to cash out the leaves. No more guessing how tall or bushy a tree might be — the arithmetic is fixed. Long, thin paths in such a tree are forced once n is large, and that single fact is the engine behind the context-free pumping lemma.

Here is the link spelled out. The context-free pumping lemma says: every context-free language has a constant p such that any string of length at least p can be split into five pieces u v x y z, where the middle v x y is short, v y together is non-empty, and pumping — repeating v and y in lockstep — keeps you inside the language. Where does that p come from? From a CNF grammar. If a string is long enough, its binary parse tree must be tall; a tall thin branch must repeat some variable A on a single root-to-leaf path (the pigeonhole principle in disguise). That repeated A is a loop you can run again and again — and 'running it again' is exactly pumping v and y.

And why CYK can decide membership in cubic time

The second great payoff is parsing. The CYK algorithm answers the membership question — is this specific string w in the language? — and it REQUIRES the grammar to be in Chomsky normal form. Its whole strategy leans on the binary split: because the top rule must be S → B C, the string w must break into a left part generated by B and a right part generated by C. CYK does not guess where; it tries EVERY split point and remembers results in a table so it never recomputes the same subproblem. That table-filling is the heart of dynamic programming.

  1. Length-1 cells: for each single letter w[i] of the input, record every variable A with a rule A → w[i]. This is the only place the terminal rules A → a are used — to seed the table.
  2. Longer spans: to fill the cell for a substring of length L, try every way to cut it into a left part and a right part. If some variable B can generate the left part and C the right part AND the grammar has a rule A → B C, then A can generate the whole span. Record A.
  3. Build upward from short spans to the whole string. The string w is in the language exactly when the start symbol S lands in the top cell — the one covering all of w. Reading the table backwards reconstructs an actual parse tree.

Count the work: there are about n^2 / 2 substrings to consider, and filling each one tries up to n split points, giving O(n^3) time for a string of length n (treating the grammar size as a fixed constant). That is the famous cubic bound. It is a concrete, honest proof that membership in a context-free language is decidable — and not merely decidable but polynomial-time. None of this machinery would even type-check on a ragged grammar; the binary shape of CNF is what makes the 'cut into two parts' loop possible at all.

How to convert: the four moves, in order

Converting any cleaned grammar to Chomsky normal form is a short recipe, and ORDER matters for the same reasons it mattered in guide 2 — a later step can re-create the very rules an earlier step removed if you run them backwards. The first three moves are the cleanup you already know; the last two reshape what survives. We bundle them as four conceptual moves below.

  1. Clean first (and add a fresh start symbol). Introduce a new start symbol S0 → S so the start never appears on a right-hand side; then remove epsilon-productions, then unit productions, then useless symbols — exactly the disciplined order from the previous guide. After this the grammar has no A → ε (except possibly S0 → ε) and no A → B.
  2. Pull terminals out of long rules. Any rule whose right-hand side has length 2 or more but mixes in a terminal a is illegal (e.g. A → a B). For each terminal a, invent a dedicated variable Ta with the single rule Ta → a, and replace a inside long rules by Ta. Now A → a B becomes A → Ta B and Ta → a — both legal shapes.
  3. Break long right-hand sides into binary chains. A rule like A → B C D E still has too many symbols. Split off two at a time with fresh helper variables: A → B X1, X1 → C X2, X2 → D E. The new variables X1, X2 exist only to hold the leftover tail, turning one wide rule into a cascade of strict A → B C rules.
  4. Check the residue. After moves 2 and 3, every rule is either A → B C (two variables) or A → a (one terminal), with the lone tolerated S0 → ε if epsilon is in the language. That is Chomsky normal form. Nothing else needs touching.
Start (already epsilon/unit/useless-cleaned):
    S -> a S b | a b

Step 2  (pull terminals out: Ta -> a,  Tb -> b):
    S  -> Ta S Tb | Ta Tb
    Ta -> a
    Tb -> b

Step 3  (binarise the length-3 rule  S -> Ta S Tb):
    S  -> Ta X1
    X1 -> S Tb
    S  -> Ta Tb
    Ta -> a
    Tb -> b

Now every rule is  A -> B C  or  A -> a .   This is CNF.
Converting S -> a S b | a b (the a^n b^n grammar) to Chomsky normal form: one terminal-extraction pass, then one binarisation pass. The helper X1 holds the leftover 'S Tb' tail.

The honest cost: blow-up and a flattened tree

Now the warning the textbooks sometimes mumble. These conversions are not free. Removing epsilon-productions alone can roughly square the number of rules, because a rule with k nullable symbols expands into up to 2^k variants (every subset of those symbols either kept or dropped). The terminal-extraction and binarisation passes add still more helper variables. The standard guarantee is that the final CNF grammar's size is polynomial in the original — but the constant can be unpleasant, and a careless ordering (especially removing unit rules before epsilon rules) can make it dramatically worse. This is the normal-form blow-up, and it is real.

The subtler cost is that the parse trees CHANGE. Your beautiful original grammar may have grouped an arithmetic expression so each plus sign sat at one tidy node with three children — operand, plus, operand. After binarisation those helper variables like X1 splice themselves into the tree, and an operator that used to be one flat node becomes a little staircase of two-child nodes. The string generated is identical, and the set of strings — the language — is untouched, but the SHAPE of the structure you read off the tree is no longer the shape you designed. The yield survives; the silhouette does not.

So treat Chomsky normal form as an INTERNAL tool, not a final product to admire. It is the input format the CYK algorithm insists on and the lever that makes the pumping lemma provable — both jobs care only that the language is preserved and the branching is binary, not that the tree is pretty. When you actually want a meaningful tree for a compiler, you parse with your own well-designed grammar and reserve CNF for the proofs and the deciders. The next guide turns to a different normal form, Greibach normal form, whose every rule starts with a terminal — built not for binary trees but for top-down parsing and a clean link to pushdown automata.