GATE CS 2007 Q78 — Parsing (LL, LR)

By analyzing the production rules, we can determine the language generated by each non-terminal:

• $S$ generates strings with an equal number of $a$'s and $b$'s.
• $A$ generates strings with one more $a$ than $b$'s.
• $B$ generates strings with one more $b$ than $a$'s.

We can verify this property from the rules:

• $S \rightarrow aB \mid bA$: Since $B$ has one more $b$ than $a$, prepending $a$ results in an equal number of $a$'s and $b$'s. Similarly, prepending $b$ to $A$ results in an equal number of $a$'s and $b$'s.
• $B \rightarrow b \mid bS \mid aBB$: Each alternative guarantees exactly one more $b$ than $a$.
• $A \rightarrow a \mid aS \mid bAA$: Each alternative guarantees exactly one more $a$ than $b$.

Now, let's count the number of $a$'s and $b$'s in each option:

• (A) $aaaabb$: $4$ $a$'s, $2$ $b$'s (not equal)
• (B) $aabbbb$: $2$ $a$'s, $4$ $b$'s (not equal)
• (C) $aabbab$: $3$ $a$'s, $3$ $b$'s (equal)
• (D) $abbbba$: $2$ $a$'s, $4$ $b$'s (not equal)

Thus, only option C can be generated by the grammar. The derivation for $aabbab$ is: