GATE CS 2026 Set 1 — Question 25

To determine the properties of the grammar $S \rightarrow aSbS \mid bS \mid \epsilon$, let's analyze the given statements.Statement (A) and (B): Ambiguity and derivations of $abb$
We check if the string $abb$ has more than one distinct derivation (parse tree).Derivation 1:$$S \Rightarrow aSbS \Rightarrow a\epsilon bS \Rightarrow ab(bS) \Rightarrow abb\epsilon = abb$$(Here, the first $S$ becomes $\epsilon$, and the second $S$ becomes $bS \to b\epsilon$)Derivation 2:$$S \Rightarrow aSbS \Rightarrow a(bS)bS \Rightarrow ab\epsilon b\epsilon = abb$$(Here, the first $S$ becomes $bS \to b\epsilon$, and the second $S$ becomes $\epsilon$)Since there are two distinct leftmost derivations (and thus two distinct parse trees) for the string $abb$, the grammar is ambiguous. Therefore, statement (A) is true and statement (B) is true.Statement (C): Derivation of $abab$
We need to generate $abab$ starting from $S$. Since the string starts with $a$, we must use the production $S \to aSbS$.$$S \Rightarrow a S_1 b S_2$$We need $a S_1 b S_2 = abab$, which implies $S_1 b S_2 = bab$.
Possible splits for $S_1$ and $S_2$ based on the position of $b$ in $bab$:Let's check validity:

• Case 1 ($S_1 = \epsilon, S_2 = ab$): $S \to \epsilon$ is valid. Does $S \to ab$? Yes, $S \Rightarrow aSbS \Rightarrow a\epsilon b\epsilon = ab$. This gives one valid derivation.
• Case 2 ($S_1 = ba, S_2 = \epsilon$): Does $S \to ba$? The productions are $S \to aSbS$ (starts with $a$), $S \to bS$ (starts with $b$), $S \to \epsilon$. To generate $ba$, we must start with $S \to bS$. Then we need $S \to a$. However, any derivation from $S$ starting with $a$ must use $S \to aSbS$, which introduces a $b$. Thus, $S$ cannot generate the string $a$. Consequently, $S$ cannot generate $ba$. This case is invalid.

Since only one valid split exists, and the derivations for the substrings $\epsilon$ and $ab$ are unique (as shown above), the string $abab$ has a unique parse tree and thus a unique rightmost derivation. Therefore, statement (C) is true.Statement (D): Decidability
The language generated by any Context-Free Grammar (CFG) is a Context-Free Language (CFL). The membership problem for CFLs is decidable (e.g., using the CYK algorithm). Therefore, the language is decidable. Statement (D) is false.Conclusion: Statements (A), (B), and (C) are true.