Question

Consider the grammer given below:

$S\to xB\mid yA$

$A\to x\mid xS\mid yAA$

$B\to y\mid yS\mid yBB$

Consider the following strings.

(i) xxyyx

(ii) xxyyxy

(iii) xyxy

(iv) yxxy

(v) yxx

(vi) xyx

Which of the above strings are generated by the grammer?

• A. (iii) and (iv)
• B. (i), (iii) and (iv)
• C. (i), (ii) and (iii)
• D. (ii), (v) and (vi)

Answer 1

The correct option is A (iii) and (iv)

This grammer cannot generate any string starting with xx or ending with xx so (i), (ii) and (v) cannot be generated by the grammer. xyx also cannot be generated by the grammer. The derivation for (iii) xyxy and (iv) yxxy is shown below

$S\to xB\to xyS\to xyxB\to xyxy$

$S\to yA\to yxS\to yxxS\to yxxy$

So only (iii) and (iv) can we derived from this grammer.