from it. The case just mentioned is of this kind. Another reason a variable may
be useless is shown in the next grammar. In a grammar with start symbol S and
productions
the variable B is useless and so is the production B → bA. Although B can derive
a terminal string, there is no way we can achieve
.
This example illustrates the two reasons why a variable is useless: either
because it cannot be reached from the start symbol or because it cannot derive a
terminal string. A procedure for removing useless variables and productions is
based on recognizing these two situations. Before we present the general case
and the corresponding theorem, let us look at another example.
Example 6.3
Eliminate useless symbols and productions from G = (V,T,S,P), where V = {S, A,
B, C} and T = {a, b}, with P consisting of
First, we identify the set of variables that can lead to a terminal string.
Because A → a and B → aa, the variables A and B belong to this set. So does S,
because S ⇒ A ⇒ a. However, this argument cannot be made for C, thus
identifying it as useless. Removing C and its corresponding productions, we are
led to the grammar G 1 with variables V 1 = {S, A, B}, terminals T = {a}, and
productions