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
X -> ad
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
X -> ad

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

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.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.