Consider the grammar given below S → x B | y A A → x | x S | y A A B → y | y S…
2007
Consider the grammar given below
S → x B | y A
A → x | x S | y A A
B → y | y S | x B B
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 grammar ?
- A.
(i), (ii), and (iii)
- B.
(ii), (v), and (vi)
- C.
(ii), (iii), and (iv)
- D.
(i), (iii), and (iv)
Attempted by 15 students.
Show answer & explanation
Correct answer: C
To determine which strings are generated by the grammar, we analyze derivations starting from S. The grammar has productions: S → xB | yA, A → x | xS | yAA, B → y | yS | yBB. We check each string for a valid derivation from S.
(i) xxyyx: S → xB → xxBB → xxyB → xxyyS → xxyyxA / xxyyxB. Invalid.
(ii) xxyyxy: S → xB → xxBB → xxyB → xxyyS → xxyyxB->xxyyxy. Valid.
(iii) xyxy: S → xB →xyS → xyxB->xyxy. Valid.
(iv) yxxy: S → yA → yxA → yxxB → yxxy. Valid.
(v) yxx: S → yA → yxA → yxxB, but B cannot produce empty string. Invalid.
(vi) xyx: S → xB → xxB → xxy, but this does not produce xyx. Invalid.
Valid strings are (ii) xxyyxy ,(iii)xyxy and (iv) yxxy. The correct answer is option 3.
A video solution is available for this question — log in and enroll to watch it.