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 -> a
We 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
