Eliminating ε-Productions
You'll learn how to remove nullable productions (A → ε) from context-free grammars without changing the language they generate.
What Are ε-Productions?
In context-free grammars, an ε-production is a rule where a non-terminal produces the empty string: A → ε. These productions can make grammars harder to analyze and convert to normal forms like Chomsky Normal Form (which forbids ε-productions except under special conditions).
Why Remove Them?
While ε-productions are sometimes convenient for expressing patterns (like optional elements), they're not strictly necessary. Any language generated by a grammar with ε-productions can also be generated by an equivalent grammar without them—as long as the empty string itself isn't required in the language.
The Elimination Process
The key insight: if A can derive ε, then anywhere A appears on the right side of a production, we need to account for the possibility that A "disappears."
Steps:
- Find nullable non-terminals: identify all non-terminals that can derive ε (directly or through a chain)
- Generate alternate rules: for each production containing nullable non-terminals, create new versions with those symbols present and absent
- Remove ε-productions: delete all
A → εrules - Special case: if the start symbol was nullable and the empty string is in the language, add
S' → ε | Swith a new start symbol
Example: If you have A → ε and B → aAb, create both B → aAb and B → ab (where A vanished). Then remove A → ε.
Key Takeaway: Every grammar with ε-productions can be transformed into an equivalent grammar without them by systematically accounting for nullable non-terminals in all productions where they appear.