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

«
»
In this tutorial we define those symbols that do not participate in derivation of any string, i.e. the useless symbols, and remove the useless productions from the grammar.
A symbol X is useful if:

1. If X is generating, i.e., X =>* w, where w ϵ L(G) and w in Vt*, 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
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

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

A and Z is a useful symbol as it can be derived to a string of terminal symbol (Z -> z and A -> xyz). X and Y are not useful. So all the production with X and Y in them should be removed to eliminate non-generating symbols. The grammar then becomes
A -> xyz
Z -> Zy / z
Since A is the starting symbol this implies Z is the non-reachable symbol. So we remove it to get a grammar free of useless symbols:
A -> xyz

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. 