GATE CS 2007 Q79 — Parsing (LL, LR)

To find the number of derivation trees for the string $aabbab$, we trace the leftmost derivations step-by-step starting from the start symbol $S$:

1. Since the string starts with $a$, the first production must be: $$S \rightarrow aB$$
2. The second symbol is also $a$, so we must expand $B$ using $B \rightarrow aBB$: $$S \rightarrow aB \rightarrow aaBB$$

Now, we need to derive the remaining substring $bbab$ from the two non-terminals $BB$. Each $B$ must derive a substring $w_i$ such that $w_1 w_2 = bbab$. Since any string derived from $B$ has one more $b$ than $a$, its length must be odd. Thus, the only possible odd-length partitions of the $4$-character string $bbab$ are:

• Case 1: $|w_1| = 1$ and $|w_2| = 3 \implies w_1 = b$ and $w_2 = bab$.
  • $B \Rightarrow b$ (unique derivation)
  • $B \Rightarrow bS \Rightarrow baB \Rightarrow bab$ (unique derivation)
  This yields the first derivation tree.


• Case 2: $|w_1| = 3$ and $|w_2| = 1 \implies w_1 = bba$ and $w_2 = b$.
  • $B \Rightarrow bS \Rightarrow bbA \Rightarrow bba$ (unique derivation)
  • $B \Rightarrow b$ (unique derivation)
  This yields the second derivation tree.

Since both cases yield exactly one unique derivation tree, there are a total of 2 derivation trees for the string $aabbab$.