## Elimination of Useless production/symbols from context free grammar

Condition of Useless Symbol :

We will entitle any variable useful only when it is deriving any terminal.

And also if a symbol is deriving a termial but not reachable from Start state.

**Note: All terminals will be useful symbols**

We will understand the concept using below example:

S -> AB/a A -> BC/b B -> aB/C C -> aC/B Solution: Useful Symbols: {a, b, S, A} And any combination of useful symbols will also make LHS a useful symbol. So we could see that Symbol B and C are useless symbol, remove them (whole production in which it contains): S -> a A -> b But cause A is not reachable so we will remove A -> b as well:We will see one more example:S -> a

S -> AB/AC A -> aAb/bAa/a B -> bbA/aaB/AB C -> abCA/aDb D -> bD/aC Solution: First find out useful Symbols: {a, b, A, B, S} And useless symbols are: {C, D} So remove them and write the whole grammar again:S -> AB A -> aAb/bAa/a B -> bbA/aaB/AB