search
Log In
18 votes
2k views

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$
in Compiler Design
edited by
2k views
0
0
@Praveen Saini is there any method we can find directly without using trial and error method for finding number of derivation trees.
0
AFAIK , there is no direct way.

But I think It is possible by modification in CYK (if try)

2 Answers

28 votes
 
Best answer
$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
11
sir by using trial and error method for finding number of derivation trees there may be chances that we missed out some. can you suggest something else
3

I don't think that there will  be algorithm to find number of parse tress given a grammar.If it would have been possible, then problem whether a CFG G is ambiguous would be decidable which is already proven to be undecidable. 

@Arjun can this be the reasoning for not having any method to derive number of parse trees given a grammar G.

0

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

 

0 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

19 votes
2 answers
1
3.7k views
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$ ... $B \rightarrow aBB$ $S \rightarrow bAA$ Which of the following strings is generated by the grammar? $aaaabb$ $aabbbb$ $aabbab$ $abbbba$
asked Sep 22, 2014 in Compiler Design Kathleen 3.7k views
49 votes
9 answers
2
13.3k views
Consider the following two statements: P: Every regular grammar is LL(1) Q: Every regular set has a LR(1) grammar Which of the following is TRUE? Both P and Q are true P is true and Q is false P is false and Q is true Both P and Q are false
asked Sep 22, 2014 in Compiler Design Kathleen 13.3k views
20 votes
5 answers
3
4.2k views
Consider the grammar with non-terminals $N=\left\{S,C,S_1\right\}$, terminals $T=\left\{a, b, i, t, e\right\}$, with $S$ as the start symbol, and the following set of rules: $S \rightarrow iCtSS_1 \mid a$ $S_1 \rightarrow eS \mid \epsilon$ $C \rightarrow b$ The grammar is NOT LL(1) because: it is left recursive it is right recursive it is ambiguous it is not context-free
asked Sep 22, 2014 in Compiler Design Kathleen 4.2k views
12 votes
4 answers
4
2.5k 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.
asked Sep 22, 2014 in Compiler Design Kathleen 2.5k views
...