Question

Find Consider the following context-free grammar G:
S --> T#T
T --> C
A --> aA | epsilon
B --> bB | epsilon
C --> cC
C --> c
a) Give the set of unproductive symbols in G?
b) Give an equivalent grammar without useless symbols.

Answer 1

Given grammar G:

S --> T#T
T --> C
A --> aA | epsilon
B --> bB | epsilon
C --> cC
C --> c

Question a) Give the set of unproductive symbols in G?

Answer: Unproductive symbols in a grammar are the symbols that cannot be generated by any means from the start symbol. It is similar to useless symbols. It is also said that a symbol is productive if the right hand side of its production rule contains productive symbols. In the given grammar, non-terminal A and B is not present in the right hand side of any of the rules except they can generate themselves only. Thus, A and B are not productive symbols, i.e. they cannot be used to generate any string in the given grammar. Also, only non-terminals can be unproductive only.

Thus, the set of unproductive symbols in G is: {A, B}

Question b) Give an equivalent grammar without useless symbols.

Answer: In a grammar, a symbol is called useless if it does not appear in the Right hand side of any production rule of the grammar, that can be reached from the start symbol. In other words, the useless symbols does not contribute in production of any string.

In the given grammar, the start symbol is S. Which generates non-terminal T and non-terminal T generates non-terminal C. Non-terminal C can recusrively generates itself. Thus, non-terminals A and B are unreachable from the start symbol S. Thus, A and B are useless symbols.

Now, the grammar containing any production rule(s) from these useless symbols can be removed without any issue, since they does not contribute in any production. So, the production rules, A --> aA | epsilon and B --> bB | epsilon has to be removed.

The revised grammar without any useless symbols:

S --> T#T
T --> C
C --> cC
C --> c

NOTE: The two production rules from C can be merged into a single one, which will reduce the number of rules but maintaining the grammar unchanged. The grammar is given below:

S --> T#T
T --> C
C --> cC | c