Mathematical Foundation of Computer Science

DHARM

308 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

begin

Old V = ∅;

New V = {A ∈ VN / A → α is in P and α ∈ VT*)

While (old V < > new V) do

Begin

Old V = new V

New V = new V ∪ {A ∈ VN /A generates α is in P,

so α ∈ (VT ∪ old V*}

end;

end.

Fig. 11.21

Reachable Symbol

If there exist the derivation S ⇒N α X β (for some α and β) then symbol X is said to be reachable

symbol. Start symbol is always consider as a reachable symbol. Now we discuss the Algorithm
to find useful symbol:
Step 1. Find active non terminals and drop rest of the non active non terminals from the
grammar.
Step 2. Find reachable symbols and remove non reachable symbols from the grammar.

Example 11.26. A grammar G is given, find an equivalent grammar with no useless symbols.
S → a | AB
A → a | aA
B → bB | aB
C → d | dC
Sol. l First,we will find active non terminals, these are {S, A, C} all these generated termi-
nal strings.
(Symbol B is not active non terminal because it’s not generate the terminal string)
So, we have following grammar
S → a | AB
A → a | aA
C → d | dC
l Now, we will find reachable symbols.
From S symbol ‘a’ is generated so ‘a’ is reachable. Symbols A and B are also reachable
but fortunately, there is no production derive from B so it is a useless hence S derive AB is
useless and drop both symbols. Clearly, C is non reachable symbol so drop C. Therefore, only
reachable symbols are {S, a}.
Hence, the grammar G left with a single useful production
S → a
Example 11.27. A grammar G is given, find an equivalent grammar with no useless symbols.
S → AB | AC
A → aAb | bAa | a
B → bbA | aaB | AB