Context-Free Languages: Simplification & Normal Forms

removing unit productions

If contact A says 'see B', and B says 'see C', and C finally lists a real number, you can save everyone time by writing that number straight into A. Removing unit productions does this short-circuiting for a grammar: you trace every chain of variable-to-variable renames and copy the real, content-bearing rules to the top so the renames can be deleted.

The method uses unit pairs. A pair (A, B) is a unit pair if A can derive B using only unit productions — including (A, A) trivially. You compute all unit pairs by following chains: if (A, B) is a unit pair and B -> C is a unit production, then (A, C) is too. Then, for every unit pair (A, B), you add to A every NON-unit rule of B; that is, if B -> alpha is not itself a unit production, you add A -> alpha. Finally you delete all unit productions. The resulting grammar generates the same language but contains no rule of the form variable -> single variable.

This step comes after epsilon-production removal, for a concrete reason: eliminating epsilon-productions can turn a two-symbol rule into a one-variable rule (for instance, A -> BC with B nullable yields A -> C, a brand-new unit production), so you must clean epsilon first or you will leave units behind. Removing unit productions is required for Chomsky normal form. It can increase the number of rules, since each variable inherits the non-unit rules of everything it can reach by renaming, but the growth is modest compared with the epsilon and CNF-binarization steps.

E -> E+T | T, T -> T*F | F, F -> (E) | a. Unit pairs include (E,T),(E,F),(T,F). Copying non-unit rules upward: E -> E+T | T*F | (E) | a, T -> T*F | (E) | a, F -> (E) | a. The renames E->T, T->F are gone; the language is unchanged.

Each variable absorbs the real rules of everything reachable by renaming, then the renames vanish.

Do unit removal AFTER epsilon removal but BEFORE deleting useless symbols. Removing units can expose new non-generating or unreachable symbols, so the useless-symbol pass should be the last cleanup step.

Also called
unit eliminationchain-rule removalunit-pair method單位產生式消除單位對方法