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

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.

---

Quickest way to do this type of question is to draw a machine. 

correct @Shaik Masthan sir ?

---

Quickest way to do such question is to do without pen and paper

just see options ,which ouy 1 to 6 comes most ,you will say ii ,now which is the second most occurring ,you will say iii ,so now just draw for ii and iii are they belongs ,and this

way you willl do this type of question in 2 min ,30 s observation and 90 so to figure out that your observation is correct.

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

then why not ii?

---

yes you are right ..

ii) iii) and iv) option C is correct .

---

only 3rd and 4th are possible. if B ------ > yl yys l xBB then 2nd is also possible.

---

@praveen sir, can u give parse tree for (ii) ?

i do not know how two conjugative x can be generated

---

Actually I strongly believe there  is misprint in question,  there should be $B\rightarrow xBB$ instead of $yBB$

As far as I know,  it is very common language of equal equal 

---

S->XB

B->XBB

B->yS,B->y

S->yA

A->X you will get xxyyxy which is string number 2.

---

(i) can be generated...

A->XB->XXBB->XXYS->XXYYA->XXYYX

 

what's wrong with this???? please tell me

---

A->XB->XXBB->XXYS[B]

---

after solving option a i am getting 

1.  xxyyxx
2.  xxyyxyxx
3.  xyxy

what is wrong here 

1.

-->xxS

-->xxyA

-->xxyyAA

-->xxyyxx

---

 

(i) xxyyx

First part is also generated.

A->XB->XXBB->XXYS->XXYYA->XXYYX

What is problem with it ?

---

also it can't generate odd length string

---

@Kuljeet Shan problem is (i) is,

S---> XB

------>XXBB

------->XXYB

------->XXYYS

------>XXYYXB 

it is not possible to get "xxyyx"

---

@Praveen Saini sir is it possible to draw dfa for this?

but i think the given grammar is not regular so DFA is not possible right?

---

@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.

---

Another equivalent version of grammar which generates equal number of a's and b's (inclduing $\epsilon$)

https://cs.stackexchange.com/questions/64569/unambiguous-grammar-that-produce-equal-number-of-a-and-b

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