GATE CS 2024 Set 2 Q42 — Parsing (LL, LR)

We can analyze the relationship between the counts of symbols by observing how the variables and terminals are generated in the grammar $G$:

1. Relation between $n_c(w)$ and $n_b(w)$ (Option C):
   • We start with a single start symbol $S$.
   • The rule $S \rightarrow aS$ maintains the number of $S$ variables.
   • The rule $S \rightarrow aSbS$ increases the number of $S$ variables by $1$ and introduces exactly one $b$.
   • The rule $S \rightarrow c$ replaces each $S$ with exactly one $c$.
   Thus, the total number of $S$ variables generated (and subsequently replaced by $c$) is always $n_b(w) + 1$. Therefore, $n_c(w) = n_b(w) + 1$ is always true. This validates Option C and disproves Option D.
2. Relation between $n_a(w)$ and $n_b(w)$ (Option B):
   • Every $b$ is introduced only via the rule $S \rightarrow aSbS$, which also introduces an $a$.
   • The rule $S \rightarrow aS$ introduces an $a$ without introducing any $b$.
   Therefore, $n_a(w) \ge n_b(w)$. Substituting $n_b(w) = n_c(w) - 1$, we get: $$n_a(w) \ge n_c(w) - 1 > n_c(w) - 2$$ Thus, $n_a(w) > n_c(w) - 2$ is always true. This validates Option B.

Counterexample for Option A: For the string $w = c \in L(G)$, we have $n_a(w) = 0$ and $n_b(w) = 0$. The inequality $0 > 0$ is false, so Option A is incorrect.