Eliminating Unit Productions
What You'll Learn
You'll learn how to systematically remove single nonterminal productions (like A → B) from context-free grammars to simplify their structure without changing the language they generate.
What Are Unit Productions?
A unit production is a grammar rule where one nonterminal produces exactly one other nonterminal, like A → B. These rules don't add expressive power—they just create "shortcut" chains between nonterminals—but they complicate grammar analysis and parsing algorithms.
Think of unit productions like forwarding addresses: if mail for person A gets forwarded to person B, who forwards it to person C, who finally opens it at their home address, you could eliminate the middlemen by sending directly to C's home.
Why Eliminate Them?
Unit productions bloat parse trees and make algorithms like the CYK parser less efficient. After eliminating ε-productions, removing unit productions is the next step toward normalized grammar forms like Chomsky Normal Form.
The Elimination Algorithm
-
Find all unit pairs: For each nonterminal
A, determine which nonterminalsBare reachable through chains of unit productions (e.g.,A → B → CmeansAcan reach bothBandC). -
Replace unit productions: For each unit pair
(A, B)whereAreachesB, add new productionsA → αfor every non-unit productionB → α. -
Delete all unit productions: Remove every rule of the form
A → B.
Example
Given: S → A, A → B, B → a | b
SreachesAandB- Add:
S → a | bandA → a | b - Remove:
S → A,A → B - Result:
S → a | b,A → a | b,B → a | b
Key Takeaway: Eliminating unit productions removes nonterminal-to-nonterminal chains by replacing them with direct rules to terminal strings, simplifying the grammar while preserving its language.