Question 52

In any derivation starting from $S$, suppose the rule $S \rightarrow aS$ is applied $m \ge 0$ times, and the rule $S \rightarrow aSbS$ is applied $k \ge 0$ times:

• Each application of $S \rightarrow aSbS$ increases the number of nonterminal $S$ instances by $1$, while $S \rightarrow aS$ keeps the number of $S$ instances unchanged. Starting with $1$ instance of $S$, the total number of $S$ instances that eventually terminate via $S \rightarrow c$ is $k + 1$.
• Counting terminal occurrences in $w$:
  • $n_b(w) = k$
  • $n_c(w) = k + 1 = n_b(w) + 1 \implies$ (C) is TRUE (and (D) is FALSE).
  • $n_a(w) = k + m \ge k = n_b(w)$.
• Checking (A): When $m = 0$ (e.g., $w = c$, where $k = 0, m = 0$), $n_a(w) = 0 = n_b(w)$, so $n_a(w) > n_b(w)$ is FALSE.
• Checking (B): Since $n_a(w) = k + m \ge k$ and $n_c(w) - 2 = (k + 1) - 2 = k - 1$, we always have $n_a(w) \ge k > k - 1 = n_c(w) - 2$, so (B) is TRUE.