Kindly consider the following productions. How can I identify a useless production?
S->aS|A|C
A->a
B->aa
C->aCb
Somebody please guide me. Zulfi.
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Starting from $S$ it is impossible to generate a sentential form that contains the nonterminal $B$.
This is easy to see since:
$S$ only has productions whose body contain $S$ itself, $A$ or $C$.
$A$ has no nonterminals in the body of its productions.
$C$ has only $C$ itself in the body of its productions.
This means that the production $B \to aa$ is useless.
$\begingroup$
$\endgroup$
Useless symbols are those that do not appear in any derivation from the start variable of some terminal string. If you similarly define useless productions to be those productions that are not used in any derivation from the start variable of a terminal string, then observe that the production $B \rightarrow aa$ is useless because $B$ is not reachable from the start variable, and the production $C \rightarrow aCb$ is also useless because it does not derive any terminal string - once we use this production, the nonterminal symbol $C$ will be contained in every further sentential form, and so we can't obtain a string containing only terminal symbols.
