Course contentsShow
← Computer Science
Lesson 1824 of 2,87241. Context-Free LanguagesFree lesson

Eliminating Unit Productions

Remove single nonterminal productions (A → B) through systematic replacement.

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

  1. Find all unit pairs: For each nonterminal A, determine which nonterminals B are reachable through chains of unit productions (e.g., A → B → C means A can reach both B and C).

  2. Replace unit productions: For each unit pair (A, B) where A reaches B, add new productions A → α for every non-unit production B → α.

  3. Delete all unit productions: Remove every rule of the form A → B.

Example

Given: S → A, A → B, B → a | b

  • S reaches A and B
  • Add: S → a | b and A → 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.