GATE CSE 2007 | Question: 78

Question

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$       $A \rightarrow bAA$

Which of the following strings is generated by the grammar?

• A. $aaaabb$
• B. $aabbbb$
• C. $aabbab$
• D. $abbbba$

Comments

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"

---

This method would work in single correct but not multiple correct

---

This grammar is ambigous.

Answer 1

$S  \rightarrow aB$
    $ \rightarrow aaBB$
    $ \rightarrow aabB$
    $ \rightarrow aabbS$
    $ \rightarrow aabbaB$
    $ \rightarrow aabbab$

Correct Answer: $C$

Comments

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

---

is there a typo here? geeks for geeks has given the grammar like this, also checked some other sites

S --> aB        S --> bA
B --> b         A --> a
B --> bS        A --> aS
B --> aBB       A --> bAA

Answer 2

Here is the answer 

 

Answer 3

ans c) b)

Comments

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