GATE 2026 CS (CS1) – Question 25
Consider the following grammar where $S$ is the start symbol, and $a$ and $b$ are terminal symbols.
$$S \to aSbS \mid bS \mid \epsilon$$
Which of the following statements is/are true?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) The grammar is ambiguous; (B) The string $abb$ has two distinct derivations in this grammar; (C) The string $abab$ has only one rightmost derivation
Explanation
Grammar: $S\to aSbS\mid bS\mid\varepsilon$.
**Ambiguity of `abb` (A and B).** Two different parse trees exist:
- Tree 1: $S\Rightarrow aSbS$, first $S\to\varepsilon$, second $S\to bS\to b$. The string is $a\cdot b\cdot b=abb$ (the two empty strings vanish).
- Tree 2: $S\Rightarrow aSbS$, first $S\to bS\to b$, second $S\to\varepsilon$. The string is $a\cdot b\cdot b=abb$ (the empty string vanishes).
So `abb` has two distinct derivations and the grammar is ambiguous. (A) and (B) are true.
**Unique derivation of `abab` (C).** Any derivation must start with $S\to aSbS$ (the string starts with `a`). Write $abab=a\,S_1\,b\,S_2$, so $S_1\,b\,S_2$ derives `bab`.
- $S_1=\varepsilon$ gives $S_2=$ `ab`, and `ab` $=a\,\varepsilon\,b\,\varepsilon$ in exactly one way.
- $S_1=b$: the next symbol must be the terminal `b`, but it is `a`. Impossible.
- $S_1=ba$: $S$ cannot derive `ba`, because every `a` produced by $S$ is followed later by a matching `b`. Impossible.
- $S_1=bab$ would leave no `b` for the middle terminal. Impossible.
So `abab` has exactly one parse tree, hence exactly one rightmost derivation. (C) is true.
**(D)** The language is context-free, so it is decidable. False.
Answer: A, B, C.