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

Eliminating ε-Productions

Remove nullable productions (A → ε) from grammars while preserving the language.

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:

  1. Find nullable non-terminals: identify all non-terminals that can derive ε (directly or through a chain)
  2. Generate alternate rules: for each production containing nullable non-terminals, create new versions with those symbols present and absent
  3. Remove ε-productions: delete all A → ε rules
  4. Special case: if the start symbol was nullable and the empty string is in the language, add S' → ε | S with 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.