GATE CS 2024 Set 2 — Question 52

Let $k_1, k_2, k_3$ be the number of times the rules $S \rightarrow aS$, $S \rightarrow aSbS$, and $S \rightarrow c$ are applied in the derivation of a string $w$, respectively.We track the number of non-terminals $S$ and the terminals generated:For a derivation to terminate and produce a string $w \in L(G)$, the final number of $S$'s must be 0. Starting from 1 $S$, the total change must be $-1$.$$0 \cdot k_1 + 1 \cdot k_2 + (-1) \cdot k_3 = -1$$$$k_2 - k_3 = -1 \implies k_3 = k_2 + 1$$The number of terminals in $w$ are:

• $n_a(w) = k_1 + k_2$ (since rules 1 and 2 produce 'a')
• $n_b(w) = k_2$ (only rule 2 produces 'b')
• $n_c(w) = k_3$ (only rule 3 produces 'c')

Now we evaluate the options:(C) $n_c(w) = n_b(w) + 1$
Substituting the counts: $k_3 = k_2 + 1$. This matches our derived constraint exactly. Thus, this statement is TRUE.(B) $n_a(w) > n_c(w) - 2$
Substitute $n_c(w) = n_b(w) + 1$:$$n_a(w) > (n_b(w) + 1) - 2$$$$n_a(w) > n_b(w) - 1$$Since $n_a(w) = k_1 + k_2$ and $n_b(w) = k_2$, this becomes:$$k_1 + k_2 > k_2 - 1 \implies k_1 > -1$$Since $k_1$ is a count of rule applications, $k_1 \ge 0$. Therefore, $k_1 > -1$ is always true. Thus, this statement is TRUE.(A) $n_a(w) > n_b(w)$$$k_1 + k_2 > k_2 \implies k_1 > 0$$This is not always true. For example, the derivation $S \rightarrow c$ has $k_1=0$. Thus, this statement is FALSE.(D) $n_c(w) = n_b(w) * 2$$$k_2 + 1 = 2 k_2 \implies k_2 = 1$$This is not always true. For example, $S \rightarrow c$ has $k_2=0$, so $1 \neq 0$. Thus, this statement is FALSE.Correct options are (B) and (C).