A CONTEXT-FREE GRAMMAR IS IN CHOMSKY NORMAL FORM IF EVERY PRODUCTION HAS ONE OF EXACTLY TWO SHAPES: A → B C two VARIABLES, and neither may be the start symbol if ε ∈ L(G) A → a a single TERMINAL plus, if the empty string is in the language, the single permitted exception S → ε where S is the start symbol, which must then appear on no right-hand side THE THEOREM: EVERY CONTEXT-FREE LANGUAGE WITHOUT ε (or with the one exception above) HAS A GRAMMAR IN CHOMSKY NORMAL FORM. The proof is the conversion algorithm below, so the result is constructive. ── WHY THIS FORM IS USEFUL ───────────────────────────────── 1. EVERY DERIVATION TREE IS BINARY. Each internal node has either two variable children or one terminal child, so the tree is a binary tree — which is what makes dynamic programming over substrings work. 2. THE DERIVATION LENGTH IS FIXED AND KNOWN. Deriving a string of length n takes EXACTLY 2n − 1 STEPS: n−1 applications of A → BC to build the binary tree, and n applications of A → a to produce the terminals. THIS IS THE KEY PROPERTY FOR PROOFS — it converts "does this grammar derive w?" from an unbounded search into a search of fixed depth, which is what makes membership decidable by exhaustive search even before CYK. 3. NO ε-PRODUCTIONS AND NO UNIT PRODUCTIONS, so a derivation never stalls or merely renames a variable. 4. IT IS THE PRECONDITION FOR CYK and for the proof of the CONTEXT-FREE PUMPING LEMMA, which relies on a long string forcing a deep binary tree and hence a repeated variable on some root-to-leaf path. ── THE CONVERSION, IN FIVE STEPS AND IN THIS ORDER ───────── THE ORDER MATTERS. Performing the steps out of sequence reintroduces the forms just removed, and this is the single most common exam error. STEP 1 — ADD A NEW START SYMBOL. Introduce S₀ → S, where S was the old start symbol. WHY: this guarantees the start symbol appears on no right-hand side, which is required if S₀ → ε must later be retained. STEP 2 — ELIMINATE ε-PRODUCTIONS. First find all NULLABLE variables: A is nullable if A → ε, or if A → X₁…Xₖ where every Xᵢ is nullable. Compute this to a fixed point. Then for every production containing nullable symbols, add all versions with those symbols omitted — but NEVER add A → ε itself. A → BC with both nullable yields A → BC | B | C. STEP 3 — ELIMINATE UNIT PRODUCTIONS (A → B). For each variable A, find every variable reachable from A by unit productions alone. For each such B, copy all of B's NON-UNIT productions to A. Then delete all unit productions. STEP 4 — REPLACE TERMINALS IN LONG RIGHT-HAND SIDES. In any production whose right-hand side has length ≥ 2, replace each terminal a by a new variable Xₐ, and add Xₐ → a. So A → aB becomes A → Xₐ B together with Xₐ → a. STEP 5 — BREAK UP LONG RIGHT-HAND SIDES. A → B₁B₂B₃…Bₖ with k ≥ 3 becomes a chain: A → B₁ Y₁ Y₁ → B₂ Y₂ ⋮ Y_{k−2} → B_{k−1} Bₖ introducing k−2 new variables. ── A FULLY WORKED CONVERSION ─────────────────────────────── GIVEN: S → A S A | a B A → B | S B → b | ε STEP 1 — new start: S₀ → S STEP 2 — ε-elimination. NULLABLE: B (directly, B → ε); then A (since A → B). S IS NOT NULLABLE — S → ASA needs S itself, and S → aB needs the terminal a. Rewriting each production with nullable symbols omitted in all combinations: S → A S A gives S → ASA | SA | AS | S S → a B gives S → aB | a A → B gives A → B (and A → ε is dropped) A → S unchanged B → b unchanged; B → ε deleted AFTER STEP 2: S₀ → S S → ASA | SA | AS | S | aB | a A → B | S B → b STEP 3 — unit elimination. Unit pairs: S₀ ⇒ S; S ⇒ S (trivial); A ⇒ B, A ⇒ S. Copy the non-unit productions: S₀ → ASA | SA | AS | aB | a S → ASA | SA | AS | aB | a A → ASA | SA | AS | aB | a | b B → b STEP 4 — terminals in long right-hand sides. Only aB is affected: introduce Xₐ → a. S₀ → ASA | SA | AS | XₐB | a S → ASA | SA | AS | XₐB | a A → ASA | SA | AS | XₐB | a | b B → b Xₐ → a STEP 5 — break up ASA, which has length 3. For S: S → A Y₁, Y₁ → S A For A: A → A Y₂, Y₂ → S A (and likewise for S₀) FINAL GRAMMAR IN CHOMSKY NORMAL FORM: S₀ → A Y₁ | S A | A S | Xₐ B | a S → A Y₁ | S A | A S | Xₐ B | a A → A Y₂ | S A | A S | Xₐ B | a | b B → b Xₐ → a Y₁ → S A Y₂ → S A EVERY PRODUCTION IS NOW EITHER TWO VARIABLES OR ONE TERMINAL. ✓ (Y₁ and Y₂ are identical and could be merged — a legitimate tidying step, but not required for correctness.)

── THE SIZE OF THE RESULT ────────────────────────────────── The conversion does not preserve grammar size: · STEP 2 can produce EXPONENTIALLY many productions in the worst case, since a right-hand side with k nullable symbols expands into up to 2ᵏ versions. · STEP 3 can produce O(n²) productions. · STEPS 4 and 5 are linear. IN PRACTICE the blow-up is modest, but the theoretical cost is worth stating: CNF BUYS ALGORITHMIC CONVENIENCE AT THE PRICE OF GRAMMAR SIZE, and the CYK algorithm's O(n³·|G|) running time depends on that |G|. ── WHAT IS PRESERVED AND WHAT IS NOT ─────────────────────── PRESERVED: the LANGUAGE. L(G′) = L(G), except for the ε handling, which is exactly why the S₀ → ε exception is stated so carefully. NOT PRESERVED: the SHAPE OF THE PARSE TREES. The CNF grammar derives the same strings, but the trees are binary and full of introduced variables such as Y₁ and Xₐ. THE ORIGINAL STRUCTURE — which operator grouped with which operand — IS RECOVERABLE, but only by mapping back through the conversion. THIS IS WHY COMPILERS DO NOT PARSE IN CNF: the tree shape is the meaning, and CNF distorts it. CNF is for ALGORITHMS AND PROOFS, not for language implementation. ALSO NOT PRESERVED: AMBIGUITY IS PRESERVED, which is worth noting explicitly. Converting an ambiguous grammar to CNF yields an ambiguous CNF grammar — the conversion cannot fix a defect that lies in the language's structure. ── THE CYK ALGORITHM, WHICH CNF EXISTS TO SERVE ──────────── Given a CNF grammar and a string w = a₁a₂…aₙ, build a table where V[i,j] is the set of variables deriving the substring of length j starting at position i: BASE: V[i,1] = { A : A → aᵢ is a production } STEP: V[i,j] = { A : A → BC is a production and, for some split point k with 1 ≤ k < j, B ∈ V[i,k] and C ∈ V[i+k, j−k] } ACCEPT if S ∈ V[1,n]. THE COST: n²/2 table entries, each requiring up to n splits to be tried, each checked against every production — hence O(n³·|G|). THE BINARY FORM IS ESSENTIAL: because every production splits a substring into exactly TWO pieces, there is a single split point k to iterate over. A production of length three would require two split points and a fourth power. ── COMPARISON WITH GREIBACH NORMAL FORM ──────────────────── The next topic covers GNF, and the contrast is the point: CHOMSKY NF GREIBACH NF ──────────────────────────────────────────────────────── production shape A → BC or A → a A → aα, α a string of variables every RHS two variables starts with EXACTLY or one terminal ONE terminal derivation length exactly 2n − 1 exactly n steps for a for |w| = n string of length n tree shape BINARY arbitrary branching used for CYK parsing, proving CFL = PDA, the CF pumping eliminating left lemma recursion ──────────────────────────────────────────────────────── THE UNDERLYING DIFFERENCE: CNF CONTROLS THE **SHAPE** OF THE TREE, MAKING IT BINARY SO THAT SUBSTRINGS CAN BE COMBINED PAIRWISE. GNF CONTROLS THE **PROGRESS** OF THE DERIVATION, GUARANTEEING THAT EVERY STEP CONSUMES EXACTLY ONE INPUT SYMBOL. Each normal form is designed for the algorithm it serves.