Note that the removal of the unit-productions has made B and the associated
productions useless.
We can put all these results together to show that grammars for context-free
languages can be made free of useless productions, λ-productions, and unitproductions.
Theorem 6.5
Let L be a context-free language that does not contain λ. Then there exists a
context-free grammar that generates L and that does not have any useless
productions, λ-productions, or unit-productions.
Proof: The procedures given in Theorems 6.2, 6.3, and 6.4 remove these kinds
of productions in turn. The only point that needs consideration is that the
removal of one type of production may introduce productions of another type;
for example, the procedure for removing λ-productions can create new unitproductions. Also, Theorem 6.4 requires that the grammar have no λproductions. But note that the removal of unit-productions does not create λproductions (Exercise 16 at the end of this section), and the removal of useless
productions does not create λ-productions or unit-productions (Exercise 17 at the
end of this section). Therefore, we can remove all undesirable productions using
the following sequence of steps:
1. Remove λ-productions.
2. Remove unit-productions.
3. Remove useless productions.
The result will then have none of these productions, and the theorem is proved.
productions useless.
We can put all these results together to show that grammars for context-free
languages can be made free of useless productions, λ-productions, and unitproductions.
Theorem 6.5
Let L be a context-free language that does not contain λ. Then there exists a
context-free grammar that generates L and that does not have any useless
productions, λ-productions, or unit-productions.
Proof: The procedures given in Theorems 6.2, 6.3, and 6.4 remove these kinds
of productions in turn. The only point that needs consideration is that the
removal of one type of production may introduce productions of another type;
for example, the procedure for removing λ-productions can create new unitproductions. Also, Theorem 6.4 requires that the grammar have no λproductions. But note that the removal of unit-productions does not create λproductions (Exercise 16 at the end of this section), and the removal of useless
productions does not create λ-productions or unit-productions (Exercise 17 at the
end of this section). Therefore, we can remove all undesirable productions using
the following sequence of steps:
1. Remove λ-productions.
2. Remove unit-productions.
3. Remove useless productions.
The result will then have none of these productions, and the theorem is proved.