Removing Useless Symbols
You'll learn how to identify and eliminate grammar symbols that can't participate in any valid derivation from start to goal string.
Why Clean Up Your Grammar?
After eliminating ε-productions and unit productions, your context-free grammar might still contain "dead weight"—symbols that serve no purpose. Imagine a recipe book with ingredients that are never actually used in any dish, or dishes that require ingredients you can never obtain. Useless!
A symbol is useless if it falls into either category:
- Non-generating: A nonterminal that cannot derive any string of terminals (no matter how many steps you take, you never reach a complete word)
- Unreachable: A symbol that can never appear in any derivation starting from the start symbol
The Two-Pass Algorithm
Pass 1: Remove non-generating symbols
Work bottom-up. Mark all terminals as generating (they already are terminal strings). Then iteratively mark nonterminals whose right-hand sides contain only generating symbols. Any unmarked nonterminal is non-generating—delete it and all productions containing it.
Pass 2: Remove unreachable symbols
Work top-down from the start symbol. Mark it as reachable, then mark any symbol appearing in productions of reachable nonterminals. Any unmarked symbol is unreachable—delete it and its productions.
Order matters! Always remove non-generating symbols first. Removing unreachable symbols first could leave non-generating ones behind.
Example Intuition
If A → BC but C can never produce a terminal string, then A can't either via this production. Similarly, if there's no derivation path from S (start) to a production using D, then D is unreachable dead code.
Key Takeaway: Removing useless symbols requires two passes—first eliminate non-generating symbols (bottom-up), then eliminate unreachable symbols (top-down)—to ensure your grammar contains only productive, accessible components.