DHARM304 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCEl Since, definition of production A is non terminative so it is a useless production, si-
multaneously symbol A is a useless symbol. (mark by ×)
A → a A | b A
l Because of the useless symbol A the production
S → A B has no meaning so it is a useless production.
l And because of the useless production S → A B it is meaningless to include the pro-
duction of B into the grammar.
Hence, B → a | a B becomes the useless production.
Finally, we find that S → a is the only meaningful production of the grammar.
Example 11.22. Simplify the grammar
S → a | A B | D
A → a | a A
B → b B | a B
C → d C | d
Sol. Let us find the reachable symbols of the grammar i.e.,
l a, A, B and D are reachable from S,
l b is also reachable because B is reachable,
l Nothing else is reachable.
(There is no way to reach to symbol C from Starting symbol S)
So, {S, a, A, B, D, b} are reachable symbols.
Now, from the reachable symbols find the useful symbols
l S → a is useful production,
l B is not useful because of non terminative production of B,
l S ⇒ A B ⇒ a B ⇒ ... that never reach to terminal string because of non terminative
production of B; B is useless symbol; so eliminate production S → AB.
l Because S → A B is a useless production hence it is useless to define the production of
A or A → a | a A are the useless productions.
l The deriving symbol/s from D are undefined hence S → D is useless production.
Summarize the useful symbols we find that S → a is the only production of the grammar.- Eliminate the Unit Productions
A production of form X → Y (where X and Y ∈ VN) is a unit production. These productions may
be useful or may not be useful (useless). If derivation of unit productions terminated on termi-
nals then it is useful like as, whenever, X → Y is a unit production and Y ⇒N α ∈ (VT)*, then we
can add the production X → α (after removing unit production X → Y) in the set P and when-ever, X → Y and Y → Z are unit productions and Z ⇒N α ∈ (VT)*, then we can add the production
X → α (after removing unit productions X → Y and Y → Z) in the set P. A cycle of unit produc-
tions is the case of all useless unit productions. For example, A → B, B → C, C → A are useless
productions.