Simplification and Chomsky Normal Form

Hopcroft 2e §7.1. Four constructions that must run in one particular order — ε-productions, unit productions, useless symbols, then CNF — because each can leave behind what an earlier one removed if they run the other way. Type a grammar, watch each stage work, and see the grammar diffed between stages.

Grammar — one variable per line, alternatives with |, ε for the empty production

Presets:

Symbols split per character (aSb is a, S, b) unless any alternative contains spaces — then tokens are space-separated and id stays one terminal. Variables are whatever appears left of an arrow.

3 variables {S, A, B}, 2 terminals {a, b}, start S — 7 productions.

The safe order (Theorem 7.14) — and the two order traps

The book introduces useless symbols first (§7.1.1) but prescribes running the eliminations as ε-productions, then unit productions, then useless symbols. Eliminating ε-productions can create unit productions (A → B | ε becomes A → B); eliminating unit productions can leave a variable nothing reaches. Done in the safe order, each pass only removes, and nothing the earlier passes removed comes back.

Inside the useless-symbol pass there is a second order: non-generating symbols first, then unreachable ones (Theorem 7.2). Both traps cost exactly the marks they look like they cost.