Eliminating ε- and Unit Productions

1. Eliminating ε-Productions (Null Productions)

An ε-production (or null production) is a rule of the form A → ε, where A is a variable. While useful for defining languages that include the empty string, they can complicate parsing algorithms and lead to a combinatorial explosion of derivation paths. Our goal is to remove them while preserving the language.

The core idea is to identify which variables can "vanish" (derive ε) and then explicitly create new production rules that account for their disappearance.

The Algorithm

1. Find all nullable variables: A variable A is nullable if it can derive ε. This can happen directly (if A → ε is a rule) or indirectly (if A → BC and both B and C are nullable). We find this set iteratively, much like we found generating symbols in the last lesson.
2. Construct new productions: For every production X → α in the grammar, we add new productions where every possible non-empty subset of nullable variables in α is removed.
3. Finalize the grammar: The new grammar consists of all the newly created productions plus the original non-ε, non-unit productions. The original A → ε rules are discarded.

The following video provides a clear walkthrough of this algorithm.

A Worked Example

Now, let's see this algorithm in action. The video continues with an example that demonstrates how to systematically replace nullable variables to generate the new set of productions.

Let's watch the full example from the Neso Academy video.

For those who appreciate the formal mathematical foundation, the algorithm to find nullable variables is equivalent to computing the set E(G) of "erasable" nonterminals. This is done using a fixed-point algorithm, as detailed in the resource below.

Important Note: If the start symbol S is nullable, it means the language L(G) contains the empty string ε. In this case, we typically add a new start symbol S' with productions S' → S | ε and ensure S' does not appear on the right-hand side of any production. The simplification process is then carried out on the rest of the grammar.

2. Eliminating Unit Productions

A unit production is a rule of the form A → B, where both A and B are single variables. These rules act as simple "renaming" steps in a derivation (e.g., S ⇒ A ⇒ B ⇒ ...). They add length to derivations without generating any terminals, and our goal is to bypass them.

The Algorithm

1. Identify unit production chains: For each variable A, find the set of all variables B such that A can derive B through a sequence of one or more unit productions (written as A ⇒* B).
2. Add shortcut productions: For each pair (A, B) where A ⇒* B, add a new production A → α for every non-unit production B → α.
3. Finalize the grammar: The new grammar consists of all the productions from step 2 plus all original non-unit productions. All original unit productions are removed.

Let's watch a video that explains and demonstrates this procedure.

As with ε-productions, this process can be described more formally. The algorithm involves computing, for each nonterminal A, the set I_A of all nonterminals it can derive via unit rules. You can find this formal description in the same UPenn textbook resource (LINK, section 1, Lemma 3.3.2).

3. The Correct Order of Simplification

We have now learned three simplification techniques:

1. Eliminating ε-productions.
2. Eliminating unit productions.
3. Eliminating useless symbols.

The order in which you apply these algorithms is critical. Applying them in the wrong order can lead to an incorrect or incompletely simplified grammar.

The correct order for a full simplification is:

1. Eliminate ε-productions.
2. Eliminate unit productions.
3. Eliminate useless symbols.

Why this order?

• Eliminating ε-productions can create new unit productions. For example, if you have A → BC and C is a nullable variable, the algorithm will add the new production A → B, which is a unit production. If you had already removed unit productions, you would now have to do it again.
• Eliminating unit productions can create useless symbols. As seen in the video LINK, after replacing unit rules, some variables might no longer be reachable from the start symbol. Therefore, the cleanup of useless symbols should happen last.

Conclusion

In this lesson, you have learned the systematic algorithms for removing two key types of "inefficient" productions from a Context-Free Grammar: ε-productions and unit productions.

Key Takeaways:

• ε-productions (A → ε) are removed by first identifying all nullable variables and then creating new productions that represent all the ways those variables could vanish.
• Unit productions (A → B) are removed by creating "shortcut" productions that bypass the renaming chain, directly connecting a variable to the non-unit productions of the variables it can derive.
• The order of simplification is crucial: First eliminate ε-productions, then unit productions, and finally clean up any newly created useless symbols.

Preview of the Next Lesson:
With these simplification tools in hand, our grammars are now "clean." They are free of useless symbols, ε-productions (except for S → ε if needed), and unit productions. This clean state is the perfect starting point for our next objective: converting any CFG into an equivalent grammar in Chomsky Normal Form (CNF). This highly restricted format is fundamental to many important algorithms in computer science, including parsing and deciding membership in a context-free language.