in .
Notice that, in this case, the variable B and its associated productions are still
in the grammar even though they can no longer play a part in any derivation. We
will next show how such unnecessary productions can be removed from a
grammar.
Removing Useless Productions
One invariably wants to remove productions from a grammar that can never take
part in any derivation. For example, in the grammar whose entire production set
is
the production S → A clearly plays no role, as A cannot be transformed into a
terminal string. While A can occur in a string derived from S, this can never lead
to a sentence. Removing this production leaves the language unaffected and is a
simplification by any definition.
Definition 6.1
Let G = (V, T, S, P) be a context-free grammar. A variable A ∈ V is said to be
useful if and only if there is at least one ω ∈ L (G) such that
with x, y in
. In words, a variable is useful if and only if it occurs in at
least one derivation. A variable that is not useful is called useless. A production
is useless if it involves any useless variable.
Example 6.2
A variable may be useless because there is no way of getting a terminal string