Automata

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