One language, a thousand grammars
By now you can read a context-free grammar, trace a derivation, and draw a parse tree. Here is an uncomfortable truth that came along with all that freedom: the very same language can be written by wildly different grammars. You can add a useless rule that never fires, route the start symbol through a chain of single-variable renamings, or sprinkle in rules that produce the empty string ε (epsilon) in places that contribute nothing. None of this changes the SET of strings generated — but it changes the grammar's shape enormously.
Think of it like prose versus a tax form. Two people can describe the same facts — one in flowing, idiosyncratic sentences, the other on a rigid pre-printed form with numbered boxes. Both convey the truth, but only the form can be processed mechanically: a machine knows exactly where to look because the shape is fixed in advance. A normal form for grammars is that pre-printed form. We do not throw away the messy grammar's meaning; we re-express it so every rule obeys one rigid template, and then algorithms can march across it without surprises.
So the agenda of this whole rung is two-fold, and the order matters. First, simplification: scrub out the genuine junk — symbols that can never produce a real string, symbols the start can never reach, ε-rules, and pointless renaming rules. Second, conversion: pour the cleaned grammar into one of two famous moulds, Chomsky normal form or Greibach normal form, each engineered to make a specific later algorithm work.
What kinds of mess are we cleaning?
Before naming the moulds, look at the four kinds of junk simplification removes — guide 2 will do each mechanically, but you should feel them now. A useless symbol comes in two flavours. A non-generating symbol can never, no matter how you expand it, bottom out in a string of pure terminals — like a recipe step that calls an ingredient with no recipe of its own. An unreachable symbol is one the start symbol S can never get to — a recipe in the book that nothing else ever references. Either way the symbol is dead weight: deleting it and every rule touching it leaves the language untouched.
The other two kinds are subtler because they DO contribute, just clumsily. An epsilon-production is a rule A → ε that lets a variable vanish into nothing; useful for saying 'this part is optional', but it makes derivations grow and then shrink, which later algorithms hate. A unit production is a rule A → B whose entire right-hand side is a single variable — pure bureaucracy, renaming A to B without doing real work. Both can be eliminated (paying a price we will be honest about), and once they are gone every rule does something substantive.
Chomsky normal form: every rule is binary
Once a grammar is clean, the first famous mould is Chomsky normal form (CNF). The rule is austere: every production must look like A → B C (a variable rewriting to exactly two variables) or A → a (a variable rewriting to exactly one terminal). One escape hatch: if the empty string ε is in the language, a single rule S → ε is allowed for the start symbol, and S then never appears on any right-hand side. That is the entire template — two boxes on the tax form, nothing else.
Why force everything into pairs? Because A → B C means every internal node of a parse tree has exactly two children: the tree becomes BINARY. And a binary tree over a string of length n has a beautifully predictable shape — it can be cut into a left part and a right part at every node. That single structural promise is what makes the CYK algorithm possible: it fills a table by asking, for each chunk of the input, 'which variable can generate this chunk by splitting it into a left half and a right half?' — and tests membership in O(n^3) time. The binary shape is not decoration; it is the hook the algorithm hangs on.
The same binary shape pays a second dividend on the theory side. The context-free pumping lemma — the pigeonhole principle in disguise, just as the regular one was — needs to argue that a long-enough string forces some variable to repeat on a single root-to-leaf path. A bounded branching factor (here exactly 2) is precisely what lets you bound the path length and trigger the pigeonhole: a tall enough binary tree must reuse a variable, and that repeated variable is what you 'pump'. CNF makes that counting argument clean.
Greibach normal form: every rule starts with a letter
The second mould, Greibach normal form (GNF), solves a different problem and so insists on a different shape. Every production must look like A → a α, where a is a single terminal and α is a (possibly empty) string of variables. The crucial point: each rule emits exactly ONE real terminal symbol, right at the front, and that terminal is the first thing it commits to. (Again, S → ε is permitted if the empty string is in the language.)
Why care that a terminal sits at the front? Because that is exactly what top-down parsing craves: a parser reading input left to right wants every step to consume one input letter, so it can never get stuck spinning without making progress. It also gives a clean bridge to the pushdown automaton from the earlier rung. A PDA reads a^n b^n by pushing a plate for each 'a' and popping one for each 'b'; in GNF each derivation step consumes one terminal and pushes the leftover variables α onto the stack, so a GNF grammar translates almost directly into a PDA where every move reads exactly one input symbol. The front-loaded terminal is the move trigger.
Getting a grammar into GNF, and getting top-down parsing to work at all, requires fixing one notorious defect first: left recursion, a rule like A → A α where the variable reappears immediately on its own left. A naive top-down parser facing A → A α would expand A into A α into A α α forever, never reading a single letter — an infinite loop that consumes no input. Guide 5 shows how to remove left recursion (and how to 'left factor' rules that share a common prefix). GNF's front-loaded terminal is, in part, left recursion's cure made into a law.
The honest price: blow-up and lost trees
Now the part the textbooks sometimes mumble. These conversions are not free, and pretending otherwise would be dishonest. Normal-form blow-up is real: removing ε-productions can in the worst case multiply the number of rules exponentially, because every variable that could vanish forces you to add versions of other rules both with and without it. Converting to CNF can square the grammar size or worse, and GNF conversion is harsher still. The resulting grammar is correct and machine-friendly, but it can be far larger and far less readable than the one you started with.
There is a second, subtler cost that matters whenever you care about structure, not just membership. These conversions change the parse trees. The new grammar generates exactly the same set of strings — the language is preserved, always — but a string's tree in CNF (rigidly binary, full of invented helper variables) bears little resemblance to its tree in the original grammar. If you needed the original tree to mean something (operator precedence, the shape of an expression), the converted grammar will not hand it to you directly. CNF is for DECIDING membership efficiently, not for recovering the structure you designed.
Original grammar: S -> S + S | a
(clear meaning, but ambiguous and left-recursive)
A CNF-style rewrite might invent helpers and pairings:
S -> S P | a
P -> O S
O -> + (read O as the literal '+')
Same language { a, a+a, a+a+a, ... } -- but the parse
trees are now binary and reshaped, no longer the 'flat'
familiar shape, and a brand-new helper variable appeared.The road through this rung
So that is the why. We normalise grammars because algorithms need a fixed shape to grip — a tax form, not free prose. Chomsky normal form makes trees binary so CYK can test membership in O(n^3) and so the context-free pumping lemma's pigeonhole counting goes through. Greibach normal form front-loads a terminal so top-down parsing always makes progress and a PDA falls out almost for free. And we pay for both with possible exponential blow-up and reshaped trees — a trade we make knowingly.
Guide 2 rolls up its sleeves on the cleanup itself, in the load-bearing order: useless symbols, ε-productions, and unit rules. Guide 3 builds Chomsky normal form step by step; guide 4 builds Greibach normal form; guide 5 finishes with removing left recursion and left factoring — the surgery that makes top-down parsing possible at all. Carry one sentence with you the whole way: normalising never changes WHICH strings the grammar generates, only HOW each one is built — and sometimes how big the rulebook gets.