Theory of Computation – Eliminating useless symbols from the productions in a Context Free Grammar

1. If X is generating, i.e., X =>^* w, where w ϵ L(G) and w in V_t*, this means that the string leads to a string of terminal symbols.
2. If X is reachable If there is a derivation S =>* αXβ =>^* w, w ϵ L(G), for same α and β, then X is said to be reachable.

A number that is useful is both generating and reachable. For reduction of a given grammar G:

1. Identify non-generating symbols in the given CFG and eliminate those productions which contains non-generating symbols.
2. Identify non-reachable symbols and eliminate those productions which contain the non-reachable symbols

Example: Remove the useless symbol from the given context free grammar:
S -> aB / bX
A -> Bad / bSX / a
B -> aSB / bBX
X -> SBD / aBx / ad
Solution:
A and X directly derive string of terminals a and ad, hence they are useful. Since X is a useful symbol so S is also a useful symbol as S -> bX. But B does not derive any string w in V*_t so clearly B is a non-generating symbol.So eliminating those productions with B in them we get
S -> bX
A -> bSX / a
X -> ad
In the reduced grammar A is a non-reachable symbol so we remove it and the final grammar after elimination of the useless symbols is
S -> bX
X -> ad

Question: Find the equivalent useless grammar from the given grammar
A -> xyz / Xyzz
X -> Xz / xYz
Y -> yYy / Xz
Z -> Zy / z
View Answer

Sanfoundry Global Education & Learning Series – 100+ Theory of Computation Tutorials.

If you wish to look at all Tutorials and their examples, go to Theory of Computation Tutorials.