GATE CS 2006 Q84 — Parsing (LL, LR)

The given language is $L = \{ a^i b^j \mid i \neq j \}$. This language can be partitioned into two disjoint cases:

1. Case 1 ($i > j$): More $a$'s than $b$'s. This can be written as $a^m (a^k b^k)$ where $m \ge 1$ and $k \ge 0$.
2. Case 2 ($i < j$): More $b$'s than $a$'s. This can be written as $(a^k b^k) b^n$ where $n \ge 1$ and $k \ge 0$.

Let us analyze the grammar in Option D:

• $C \rightarrow aCb \mid \varepsilon$ generates equal number of $a$'s and $b$'s: $L(C) = \{a^k b^k \mid k \ge 0\}$.
• $A \rightarrow aA \mid a$ generates one or more $a$'s: $L(A) = a^+ = \{a^m \mid m \ge 1\}$.
• $B \rightarrow Bb \mid b$ generates one or more $b$'s: $L(B) = b^+ = \{b^n \mid n \ge 1\}$.

Using these, the start symbol $S \rightarrow AC \mid CB$ generates:

• $AC \Rightarrow a^m a^k b^k = a^{m+k} b^k$ (where $m+k > k$, representing $i > j$).
• $CB \Rightarrow a^k b^k b^n = a^k b^{k+n}$ (where $k+n > k$, representing $i < j$).

Thus, Option D correctly generates the language $L$.

Why other options are incorrect:
Options A, B, and C can all generate the string $ab$ (where $i = j = 1$), which is not in $L$. For example, in Option C: $S \rightarrow AC \rightarrow \varepsilon C \rightarrow aCb \rightarrow ab$.