GATE 2026 CS1 Q.25: solution and answer

GATE 2026 · CS1Q.25 · 1 mark · MSQ

Consider the following grammar where $S$ is the start symbol, and $a$ and $b$ are terminal symbols.

S \to a S b S ∣ b S ∣ ε

Which of the following statements is/are true?

(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
(D)
The language generated by the grammar is undecidable

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

(A), (B) and (C) are true. The string abb has two parse trees, so the grammar is ambiguous. The string abab has only one parse tree, so it has only one rightmost derivation. The language is context-free, so it is decidable, which makes (D) false.

Official answer: A, B, CSource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

The grammar is $S \to a S b S ∣ b S ∣ ε$ . A nonempty string that starts with $b$ can only come from $S \to b S$ . A string that starts with $a$ can only come from $S \to a S b S$ , which splits it as $w = a x b y$ , where $x$ and $y$ are both strings that $S$ derives. Because $S \to b S$ can produce extra $b$ 's anywhere, $x$ may itself contain unmatched $b$ 's. So the $b$ written in $a S b S$ is not forced to be one particular $b$ of $w$ .
Option (B), the string $abb$ . It starts with $a$ , so the first step is $S \Rightarrow a S b S$ , and we need $x b y = bb$ . There are two splits, and both work. Split 1: $x = ε$ , $y = b$ (from $S \to b S \to b$ ). Split 2: $x = b$ (from $S \to b S \to b$ ), $y = ε$ .
These give two different leftmost derivations of $abb$ : $S \Rightarrow a S b S \Rightarrow ab S \Rightarrow abb S \Rightarrow abb S \Rightarrow a S b S \Rightarrow ab S b S \Rightarrow abb S \Rightarrow abb$ In the first, the inner $S$ goes to $ε$ and the last $S$ produces the second $b$ . In the second, the inner $S$ produces the first $b$ and the last $S$ goes to $ε$ . The parse trees are different, so $abb$ has two distinct derivations. (B) is true.
Option (A). A grammar is ambiguous if some string has two different parse trees (equivalently, two leftmost derivations). By step 3, $abb$ is such a string, so the grammar is ambiguous. (A) is true.
Option (C), the string $abab$ . It starts with $a$ , so $S \Rightarrow a S b S$ and we need $x b y = bab$ . The $b$ of the production is either the 1st or the 3rd symbol of $bab$ . If it is the 3rd, then $x = ba$ . But $S$ cannot derive $ba$ : after $S \to b S$ the rest would be $a$ , and every $a$ that $S$ produces comes from $a S b S$ , which always puts a $b$ after it. So the $b$ must be the 1st symbol: $x = ε$ , $y = ab$ .
Now $y = ab$ starts with $a$ , so $S \to a S b S$ with $x^{'} b y^{'} = b$ , which forces $x^{'} = y^{'} = ε$ . Every choice is forced, so $abab$ has exactly one parse tree. A parse tree gives exactly one rightmost derivation: $S \Rightarrow a S b S \Rightarrow a S ba S b S \Rightarrow a S ba S b \Rightarrow a S bab \Rightarrow abab$ So $abab$ has only one rightmost derivation. (C) is true.
Option (D). The language is generated by a context-free grammar, so it is context-free. Every context-free language is decidable: the CYK algorithm decides membership for any string. (D) is false.
The true statements are (A), (B) and (C).

KEY IDEA

In $S \to a S b S$ , the $b$ written in the production does not have to be the first $b$ that closes the $a$ . The production $S \to b S$ lets the inner $S$ soak up extra $b$ 's. So whenever several $b$ 's follow an $a$ , check whether more than one of them can play the part of that $b$ . In $abb$ two can, which gives two parse trees. In $abab$ only one can, because $S$ cannot derive $ba$ .

WATCH OUT FOR

Treating $S \to a S b S$ like the balanced-parentheses grammar $S \to a S b S ∣ ε$ , which is unambiguous, and so assuming the $b$ in the production must be the first $b$ that balances the $a$ . Adding $S \to b S$ breaks this: in $abb$ , either $b$ can be the matching one. A second slip is to answer (D) as true or uncertain. Every context-free language is decidable.

From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 9 CFG & PDA questions, with notes

GATE 2026 CS1 Q.25: solution and answer

Answer and solution

More CFG & PDA questions