GATE CSE 2007 | Question: 79

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$

For the string $aabbab$, how many derivation trees are there?

• A. $1$
• B. $2$
• C. $3$
• D. $4$

Comments

There is No method to find Derivation Tree of given Grammar G.

If it would have been possible, then problem whether a CFG G is ambiguous would be decidable, which is already proven to be undecidable.

---

The ans to the previous question is given in this question itself.

---

this one :- https://gateoverflow.in/1272/gate-cse-2007-question-78

Answer 1

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

$S \rightarrow aB$
    $ \rightarrow aaBB$ (till now, only $1$ choice possible)
    $ \rightarrow aabSB$ $($last time we took $B \rightarrow b$, now taking $B \rightarrow bS)$
    $ \rightarrow aabbAB$
    $ \rightarrow aabbaB$
    $ \rightarrow aabbab$

So, totally $2$ possible derivation trees.

Correct Answer: $B$

Comments

In case anyone looking for the graphical derivation trees - below is how 'aabbab' can be generated.

 

---

I think it is correctly pointed out if there had been a procedure for knowing no of parse trees possible for a string ‘w’ using a CFG, then the ambiguity problem of CFG would become decidable. Just fed the algorithm with proper input, and yeep !!  you know if its ambiguous or not. We know ambiguity of CFG is undecidable

---

in less time in exam hour how we can find out all possible tree like it will take lots of time

Answer 2

we can see that 2 diagrams are possible.

Answer 3

the given grammer will generate equal numbee rof a's and b's .The 1st production will generate an extraa a then lead to other production that generate an extraa b thus equalizing number of a's and b's. and vice versa.
To see all possible derivations just try to cnstruct parse tree by taking decision each time the derivation is as follows: S->aB;B->aBB; now 1we can derive the given string by choosing 1st B to derive a b so that other B can derive S which then give ab(since the rest part contains equal number of a's and b;s we generaate it by moving to the starting symbol) uniquely similarly you can give values interchange. so 2 parse tree.

Comments

No the given grammar will not generate equal number of a’s and b’s always. ex

S → bAA → baa

Answer 4

clearly see that there are two possible trees possible and first I have taken inthe string as you can see.

Answer 5

Here is the answer