A symbol X is useful if:

- If X is
*generating*, i.e., X =>^{*}w, where w ϵ L(G) and w in V_{t}*, this means that the string leads to a string of terminal symbols. - 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:

- Identify non-generating symbols in the given CFG and eliminate those productions which contains non-generating symbols.
- 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 -> 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]**

**Related Posts:**

- Check Automata Theory Books
- Practice Computer Science MCQs
- Check Computer Science Books
- Apply for Computer Science Internship