edited by
11,490 views
44 votes
44 votes

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$?

  1. $abab$
  2. $aaab$
  3. $abbaa$
  4. $babba$
edited by

6 Answers

Best answer
42 votes
42 votes

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

  1. $abab$
    $S \to a\boxed{S}b$
    ${\to} ab\boxed{S}ab  \to abab$
  2. $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$
  3. $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.

edited by
60 votes
60 votes
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.
2 votes
2 votes
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
2 votes
2 votes
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:

Related questions

74 votes
74 votes
8 answers
3