1.4k 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$

edited | 1.4k 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)

$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$
by Veteran (425k points)
edited
+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
+2

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.