edited by
8,293 views
29 votes
29 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$

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

  1. $1$
  2. $2$
  3. $3$
  4. $4$
edited by

4 Answers

Best answer
39 votes
39 votes
$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$
edited by
1 votes
1 votes
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.
Answer:

Related questions

75 votes
75 votes
8 answers
2
Kathleen asked Sep 21, 2014
35,342 views
Consider the following two statements:P: Every regular grammar is LL(1)Q: Every regular set has a LR(1) grammarWhich of the following is TRUE?Both P and Q are trueP is tr...
15 votes
15 votes
3 answers
4
Kathleen asked Sep 21, 2014
9,565 views
Which one of the following is a top-down parser?Recursive descent parser.Operator precedence parser.An LR(k) parser.An LALR(k) parser.