GATE CS 2006 Q85 — Parsing (LL, LR)

To find the length of the derivation for the string $a^l b^m$ (where $l \neq m$), we analyze the two possible cases based on the grammar rules:

Case 1: $l > m$

Since the number of $a$'s is greater than $b$'s, we must start with the production $S \rightarrow AC$.

• Step 1: $S \rightarrow AC$ (1 step)
• Derivation of $C \rightarrow a^m b^m$: We apply $C \rightarrow aCb$ exactly $m$ times, followed by $C \rightarrow \epsilon$ once. This takes $m + 1$ steps.
• Derivation of $A \rightarrow a^{l-m}$: We apply $A \rightarrow aA$ exactly $(l - m - 1)$ times, followed by $A \rightarrow a$ once. This takes $l - m$ steps.

Total steps for $l > m$ is: $$\text{Total} = 1 + (m + 1) + (l - m) = l + 2$$ Since $l > m$, this is equal to $\max(l, m) + 2$.

Case 2: $l < m$

Since the number of $b$'s is greater than $a$'s, we must start with the production $S \rightarrow CB$.

• Step 1: $S \rightarrow CB$ (1 step)
• Derivation of $C \rightarrow a^l b^l$: We apply $C \rightarrow aCb$ exactly $l$ times, followed by $C \rightarrow \epsilon$ once. This takes $l + 1$ steps.
• Derivation of $B \rightarrow b^{m-l}$: We apply $B \rightarrow Bb$ exactly $(m - l - 1)$ times, followed by $B \rightarrow b$ once. This takes $m - l$ steps.

Total steps for $l < m$ is: $$\text{Total} = 1 + (l + 1) + (m - l) = m + 2$$ Since $l < m$, this is equal to $\max(l, m) + 2$.

In both cases, the total number of derivation steps is $\max(l, m) + 2$.