Chomsky normal form
/ Chomsky: CHOM-skee /
Imagine forcing every branching in a family tree to be exactly a parent with two children, and every leaf to be a single named person. The tree might get taller and you might invent a few helper nodes, but its shape becomes utterly regular — and anything you want to compute over it (counting, matching, searching) becomes a clean recursion on left-child and right-child. Chomsky normal form (CNF) does this to a grammar: it forces every rule into one of two rigid shapes so parse trees are always binary.
A grammar is in CNF if every rule has one of exactly two forms: A -> BC (one variable rewriting to exactly two variables) or A -> a (one variable rewriting to a single terminal). The only permitted exception is S -> epsilon on the start symbol, used solely so the language can contain the empty string. Every context-free grammar can be converted to CNF. The construction runs after simplification (remove epsilon, units, useless symbols) and then does two shaping steps: replace each terminal that sits inside a longer rule by a new variable (e.g. turn A -> bC into A -> B' C with B' -> b), and break each right-hand side longer than two symbols into a cascade of binary rules (turn A -> XYZ into A -> X T and T -> YZ). The result generates the same language with only binary or terminal rules.
CNF is prized because binary-branching parse trees give algorithms a clean shape. The CYK parsing algorithm is a dynamic program over substrings precisely because in CNF a substring is parsed as A -> BC with B covering a prefix and C covering the rest, which fills an O(n^3) table. CNF also underpins the context-free pumping lemma and many proofs by structural induction, where a fixed branching factor keeps the case analysis manageable. The honest caveat: conversion can enlarge the grammar (typically by a constant or modest polynomial factor) and it changes the parse trees, so any semantic actions attached to the original rules must be reattached to the new ones.
Converting S -> aSb | ab: the terminals inside need helper variables A -> a, B -> b, giving S -> A S' (S' -> S B) for the first rule and S -> A B for the second. Final CNF: S -> AX | AB, X -> SB, A -> a, B -> b. Every rule is now A->BC or A->a, and aabb still derives as S => AX => A SB => A AB B => aabb.
Replace inner terminals with variables, then split long right-hand sides into binary rules.
CNF does not make a grammar more powerful — it still describes a context-free language. The single permitted epsilon-rule S -> epsilon exists only so languages containing the empty string can be expressed; no other rule may derive epsilon.