Eliminating Unit Productions

A unit production is one of the form $A\; \rightarrow\; B$, where both $A$ and $B$ are single non-terminals. What this basically says is that $A$ is the same as $B$, since any where we see one we can replace it with the other. Thus we can shorten or grammar without changing the accepted language by eliminating this type of production rule.

For any non-terminal $A$, we say that a non-terminal $B$ is $A$-derivable if there exists some derivation $A\; \rightarrow^*\; B$ . Obviously this type of derivation will be effected by the elimination of unit productions.

To eliminate unit productions from a grammar, we perform the following:

1. Eliminate all $\varepsilon$-productions from the grammar.
   (This makes the task of finding unit derivations much easier).
2. For each non-terminal $A$, and For every other non-terminal $B$ which is $A$-derivable (ie $A\; \rightarrow^*\; B$)
   • For every $B$ production rule of the form $B\; \rightarrow\; \alpha$, add a new rule to the grammar of the form $A\; \rightarrow\; \alpha$ à
3. Delete all the unit productions.