Question

Suppose A->xBz and B->y, then the simplified grammar would be:

(a) A->xyz

(b) A->xBz|xyz

(c) A->xBz|B|y

(d) none of the mentioned

I got this question by my school principal while I was bunking the class.

I would like to ask this question from CFG-Eliminating Useless Symbols topic in section Properties of Context Free Languages of Automata Theory

Answer 1

The correct choice is (a) A->xyz

For explanation: For the first step, substitute B in first production as it only produces terminal and remove B production as it has already been utilized.

We get A->xBz|xyz and now, as B has no production, we eliminate the terms which hold the variable B, thus the answer remain A->xyz.