The Gateway to Computer Science Excellence
+17 votes

Consider the CFG with $\left\{S, A, B\right\}$ as the non-terminal alphabet, $\{a, b\}$ as the terminal alphabet, $S$ as the start symbol and the following set of production rules:

$S \rightarrow aB$            $S \rightarrow bA$

$B \rightarrow b$               $A \rightarrow a$ 

$B \rightarrow bS$           $A \rightarrow aS$

$B \rightarrow aBB$       $S \rightarrow bAA$

Which of the following strings is generated by the grammar?

  1. $aaaabb$
  2. $aabbbb$
  3. $aabbab$
  4. $abbbba$
in Compiler Design by Veteran (52.2k points)
edited by | 2.8k views
S -> aA ...from where ?
how did you get 3rd step from the second step??
Hm. Sorry.    I did not notice bS is not present in production.
Grammar(DCFL) for generating equal number of $a's$ and $b's$. Excluding $\epsilon$.
Just check for equal no of a's and b's .

option C "aabbab"

2 Answers

+24 votes
Best answer
$S  \rightarrow aB$
    $ \rightarrow aaBB$
    $ \rightarrow aabB$
    $ \rightarrow aabbS$
    $ \rightarrow aabbaB$
    $ \rightarrow aabbab$

Correct Answer: $C$
by Veteran (425k points)
edited by
S->bAA ->baa

so it is not the grammer for generating equal numbers of a's and b's


     A  a

A         A aS




how will this generate aabbab? reply quick

are there two grammers here?? is the string supposed to be generated by both of them??
No it is one grammar having all these productions

as S->aB  s->bA, can be written as S->aB|bA

we need to find which of the given string can be derived by Grammar.

and then for that string , how many different derivations are possible
thanks, i was confused that how could s-> bA lead to aabbab
0 votes
ans c) b)
by Loyal (5.2k points)
no, you can not generate b) from given grammar if you try to generate b) you will get string "aabbbba" here one "a" at last position is extra

you can  generate c) only

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,512 answers
101,073 users