GATE CS 2026 Set 1 Q42 — Regular and Context-free Languages

To determine the relationship between the number of $a$'s ($n_1(s)$) and $b$'s ($n_2(s)$) in any string $s \in L(G)$, we analyze the contributions of each non-terminal symbol.

1. Analysis of $B$:
From the productions $B \rightarrow a B b \mid a b$, every production adds exactly one $a$ and one $b$. Thus, for any terminal string derived from $B$: $$n_a(B) = n_b(B)$$

2. Analysis of $A$:
Let us analyze the two productions of $A$:

• Base Case: $A \rightarrow b B a b a a$
  This production explicitly contains $3$ $a$'s and $2$ $b$'s. Since $B$ contributes equal numbers of $a$'s and $b$'s (say $k \ge 1$ of each), we have: $$n_a(A) = 3 + k, \quad n_b(A) = 2 + k$$ Clearly, $n_a(A) - n_b(A) = 1$ and $n_a(A) \le 2 n_b(A)$ (since $3 + k \le 4 + 2k$ for $k \ge 1$).
• Inductive Step: $A \rightarrow a a B B A b$
  This production adds $2$ $a$'s, $1$ $b$, two $B$'s (which add equal $a$'s and $b$'s), and one child $A$. By induction, any terminal string derived from $A$ satisfies: $$n_a(A) > n_b(A) \quad \text{and} \quad n_a(A) \le 2 n_b(A)$$

3. Analysis of $S$:
The start production is $S \rightarrow a b a A B A b b a$. The explicit terminals in this production consist of $3$ $a$'s and $3$ $b$'s. Thus, for any string $s \in L(G)$: $$n_1(s) = 3 + n_a(A_1) + n_a(A_2) + n_a(B)$$ $$n_2(s) = 3 + n_b(A_1) + n_b(A_2) + n_b(B)$$ Using our previous results:

• Since $n_a(A) > n_b(A)$ and $n_a(B) = n_b(B)$, we have: $$n_1(s) - n_2(s) = (n_a(A_1) - n_b(A_1)) + (n_a(A_2) - n_b(A_2)) \ge 1 + 1 = 2$$ Thus, $n_1(s) \ge n_2(s)$ is always true (making B true and A false).
• Since $n_a(A) \le 2 n_b(A)$ and $n_a(B) = n_b(B)$: $$n_1(s) = 3 + n_a(A_1) + n_a(A_2) + n_a(B) \le 6 + 2n_b(A_1) + 2n_b(A_2) + 2n_b(B) = 2n_2(s)$$ Thus, $n_1(s) \le 2 n_2(s)$ is always true (making D true and C false).