GATE IT 2007 | Question: 48

Question

Consider the grammar given below:

$S      \rightarrow      x \ B \mid y \ A$
$A      \rightarrow      x \mid x \ S \mid y \ A \ A$
$B      \rightarrow      y \mid y \ S \mid x \ B \ B$

Consider the following strings.

1. $xxyyx$
2. $xxyyxy$
3. $xyxy$
4. $yxxy$
5. $yxx$
6. $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

Comments

V is also correct

---

How can we draw diagram for production like

A->yAA

---

People are saying that there's misprint in this question but there is nowhere specified that "S" is the start symbol here.
Is we start with some other symbol we can get diff answers.

Answer 1

ii, iii and iv.

So, option C is correct.

Above grammar is for equal no of x and y 

from Non-terminal $S \rightarrow xB$                            

                                   $\Rightarrow xy$    [as $B \rightarrow y$ one $y$ for one $x$]                               

$S \rightarrow xB$

$\Rightarrow xxBB$   [as $B \rightarrow yBB$   one $B$ result in one $y$ for one $x$ ]

$S \rightarrow xB$

$\Rightarrow xyS$ [as $B \rightarrow yS$  one $y$ for one $x$ and start again]

Note: Same applies for string start with $y$ i.e .  $S \rightarrow yA$.

Comments

@air1ankit

Yes this is not regular grammar..

For a regular grammar, R.H.S of each production has atmost one variable.. Which is not the case here..

Hence not regular..

---

I think i, v,vi can be straight away eliminated as only even length strings are generated.

---

@chirudeepnamini, it is possible to write a CFG for a regular language, hence in general, we cannot conclude that a non-regular grammar generates non-regular languages. Here, your logic works, because the language generated by the grammar is a CFL.

Answer 2

ii) xxyyxy
S → xB
S → xxBB
S → xxyB
S → xxyyS
S → xxyyxB
S → xxyyxy

 

(iii) xyxy
S → xB
S → xyS
S → xyxB
S → xyxy

 

(iv) yxxy
S → yA
S → yxS
S → yxxB
S → yxxy