GATE CSE 2017 | Set 1 | Question: 34

Question

If $G$ is a grammar with productions

$S\rightarrow SaS\mid aSb\mid bSa\mid SS\mid\epsilon$

where $S$ is the start variable, then which one of the following strings is not generated by $G$?

• A. $abab$
• B. $aaab$
• C. $abbaa$
• D. $babba$

Comments

Just a quick trick in the provided gammer number of b's can not exceed number of a's.

---

 Chhotu

will u pls more exlpain with example

---

 

Answer 1

$S \to SaS \mid aSb \mid bSa \mid SS \mid \epsilon$

If we observe carefully the given grammar is generating all strings over $\Sigma = \{a,b\}$ having number of $b’s$ not exceeding the number of $a’s.$ So, we can straight away give answer as option D. Strings in other options can be generated as shown below.

• A. $abab$
  $S \to a\boxed{S}b$
  ${\to} ab\boxed{S}ab  \to abab$
• B. $aaab$
  $S\to \boxed{S}aS$
  $\to \boxed{S}aSaS$
  $\to a\boxed{S}aS$
  $\to aa\boxed{S}$
  $\to aaa\boxed{S}b$
  $\to aaab$
• C. $abbaa$
  $S \to \boxed{S}S$
  $\to a\boxed{S}bS$
  $\to ab\boxed{S}$
  $\to abb\boxed{S}a$
  $\to abb\boxed{S}aSa$
  $\to abba\boxed{S}a$
  $\to abbaa$

Hence strings in options A, B and C can be generated using the given grammar but not the one in option D. Answer is D.

Answer 2

If we notice the productions of this grammar

S->aSb | bSa | SS | ∈

these productions will always produce number of a's and b's equal.

Also , S-> SaS this production may add more number of a's to  number of a's and b's produced by the productions above.

So all, in all this grammar is generating Number of a's = Number of b's or Number of a's are greater than number of b's

If we check option (d), it has more number of b's than a which surely cannot in no way be generated by this grammar.

Comments

Very good approach. your answer should be the best answer.

Thanks man

---

nice catch…!! . How you could able to think …??

---

How to think duing exam like this ?

Answer 3

strings in options A, B and C can be generated using the given grammar but not the one in option D. Answer is D.

 

Answer 4

we can generate option a with following sequence of productions :
S->aSb->abSab->abab
for option b:
s->aSb->aSaSb->aSaSab->aaab
for option c:
s->SS->aSbSaS->abbSaa->abbaa

there's no set of productions from which we can babba

so answer will be D

Answer 5

Both productions S → aSb | bSa implies that if b will be there then atleast that many a's as number of b's will be there. And thus option D rule out with this observation.

Answer 6

If you see the grammar the production is not present, S->SbS, because of this , babba won’t be generated  [ it contains more b’s than a’s ].

if that production had been there then option D) babba was generated