Why bother cleaning before the normal form?
In the previous guide you saw why normal forms matter: a tidy, predictable shape of grammar lets later algorithms (parsing, membership testing, proofs) assume a fixed skeleton instead of coping with every quirk a human might write. But you cannot pour a raw grammar straight into Chomsky normal form — it usually carries three kinds of clutter that the conversion machinery chokes on. This guide is the cleanup crew: three concrete passes of grammar simplification that strip the clutter while keeping the generated language EXACTLY the same.
The three kinds of clutter are: useless symbols (variables that pull their weight in no real derivation), epsilon-productions (rules of the form A → ε that let a variable evaporate to nothing), and unit productions (rules of the form A → B that merely rename one variable to another, expanding into no actual letters). None of them is illegal — a context-free grammar is free to contain all three — but each breaks the neat 'every rule does real work' shape that normal forms demand. We remove them one pass at a time.
Pass one: removing useless symbols
A symbol is useful only if it appears in some derivation of an actual terminal string from the start symbol. To be useful a variable must clear TWO independent hurdles. First it must be generating: starting from it, you can eventually reach a string of pure terminals. A non-generating symbol is a dead end — like S → A B where A can never bottom out in real letters, so S can never finish either. Second it must be reachable: starting from S, some derivation actually arrives at a sentential form mentioning it. An unreachable symbol is an island no derivation from S ever visits.
A symbol that fails EITHER hurdle is a useless symbol and can be deleted along with every rule that mentions it. Each hurdle is computed by a simple growing-set (fixed-point) procedure. For generating: mark every variable that has a rule whose right-hand side is all terminals or ε; then keep marking any variable that has a rule whose right-hand side consists only of already-marked symbols; repeat until nothing new gets marked. For reachable: start with {S} marked, then mark every symbol that appears on the right-hand side of a rule whose left-hand variable is already marked; repeat to a fixed point.
Grammar: S -> A B | a A -> a A | a B -> S B C -> b
Step 1 generating? A yes (A -> a), S yes (S -> a), C yes (C -> b),
B NO (only rule B -> S B always still has a B; never bottoms out)
delete B and every rule using it -> S -> a A -> a A | a C -> b
Step 2 reachable from S? S yes. From S -> a, nothing else is mentioned.
A and C are never reached -> delete them.
Result: S -> a (same language { a }, all clutter gone)Pass two: removing epsilon-productions
An epsilon-production is a rule A → ε: it lets the variable A quietly disappear, contributing the empty string epsilon. Normal forms have no room for a variable that can vanish in the middle of a right-hand side, so we want them gone. The trick of epsilon-production removal is to FORESEE every place a variable might evaporate and pre-bake all the shorter alternatives, so we never actually need the vanishing act.
- Find the NULLABLE variables — those that can derive ε. Mark any A with a rule A → ε; then mark any A with a rule whose right-hand side is made entirely of already-nullable variables; repeat to a fixed point. (Same growing-set idea as before.)
- For each existing rule, generate every version obtained by deleting some subset of the nullable occurrences on its right-hand side. Rule B → X A Y with A nullable spawns both B → X A Y and B → X Y; if several occurrences are nullable, cover every combination of keep-or-drop.
- Delete every A → ε rule. Then discard any all-empty version that would re-introduce A → ε, so you never recreate what you just removed.
- One honest exception: if the ORIGINAL language contained ε itself (S can derive ε), you cannot generate ε without an epsilon-rule. The standard fix keeps a single rule S0 → ε on a FRESH start symbol S0 that appears nowhere on a right-hand side, so the lone allowed epsilon never pollutes any other rule.
Concretely, take S → A B, A → a A | ε, B → b. Here A is nullable. Expanding S → A B by the keep-or-drop rule gives both S → A B and S → B; deleting A → ε leaves A → a A and, because A could vanish, also A → a (the dropped-A version of A → a A). Final cleaned grammar: S → A B | B, A → a A | a, B → b. Trace any string both ways and you get the same language — but notice the grammar grew, and a string like 'b' now has a different, shorter tree than before. That is the cost we accepted in the note above.
Pass three: removing unit productions
A unit production is a rule of the form A → B, one variable rewriting straight into another single variable and nothing else. It does no real generating work — it is a pure rename, a bureaucratic forwarding address. Chains of them (A → B → C → ...) just shuffle a token around before the actual letters appear. Removing unit productions short-circuits these chains so that every rule produces something concrete.
The mechanism: for each variable A, find every variable B reachable from A using ONLY unit productions — call these the unit-pairs (A, B). (Compute them with the same fixed-point growing-set trick.) Then for each such pair, and for each NON-unit rule B → α (a right-hand side that is not a single variable), add the rule A → α directly to A. Finally delete all the unit productions. Now A inherits, in one hop, every concrete right-hand side it could have reached through a chain of renames.
Example: S → A, A → B | a, B → b. The unit-pairs from S are (S, S), (S, A), (S, B); from A they are (A, A), (A, B). The non-unit rules are A → a and B → b. So S inherits S → a and S → b; A inherits A → b (it already had A → a). Drop the unit rules S → A, A → B. Result: S → a | b, A → a | b, B → b. (A and B are now unreachable from S, which is a reminder that another useless-symbol sweep at the very end is often worthwhile.) Same language { a, b }, no renames left.
The order of the passes, and the honest costs
Now the punchline that ties the three passes together — the order in which you apply them is not arbitrary; do it in the wrong order and a cleanup you already finished can undo itself. The standard safe sequence is: (1) remove epsilon-productions, (2) remove unit productions, (3) remove useless (first non-generating, then unreachable) symbols. The reasoning is a chain of 'don't let earlier work reintroduce junk you removed': epsilon-removal can MANUFACTURE new unit productions (deleting a nullable symbol from B → A C can leave B → A), so do epsilon first and units second. And unit-removal can leave variables stranded with no path from S, so the useless-symbol sweep comes last to mop up.
Be honest about what these conversions cost. They are language-preserving but NOT free. The grammar can swell: epsilon-removal in particular can blow a single rule with k nullable symbols into up to 2^k variants, and converting onward to Chomsky normal form or Greibach normal form adds more — the textbook bound on the full pipeline is roughly quadratic in the grammar's size, and constants can hurt. This is the normal-form blow-up you should expect. Just as important, the parse trees change: a cleaned grammar generates the same strings but assigns them different trees, so any meaning you attach to the original tree shape (precedence, associativity) is not automatically preserved.
With the clutter gone you now have a grammar whose every rule does real work: no symbol that earns nothing, no rule that evaporates, no rule that merely renames. That is exactly the launching pad the NEXT guide needs. In guide 3 we push this clean grammar all the way into Chomsky normal form — every rule either A → B C (two variables) or A → a (one terminal) — and you will see why those strictly binary parse trees are precisely what powers the CYK parsing algorithm and the proof of the context-free pumping lemma.