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: S -> aWe will see one more example:
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