A grammar symbol $X$ (terminal or nonterminal) is useless if there is no derivation of the form $S \overset{\ast}{\Rightarrow}wXy\overset{\ast}{\Rightarrow} wxy$. That is, $X$ can never appear in the derivation of any sentence.
- Give an algorithm to eliminate from a grammar all productions containing useless symbols.
- Apply your algorithm to the grammar:
- $S\rightarrow 0\mid A$
- $A\rightarrow AB$
- $B\rightarrow 1$
