The GATE Grind

GATE 2026 CS (CS1) – Question 25

Theory of Computation · Context-Free Grammars and Pushdown Automata · 1 mark · Multiple select

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?

  1. The grammar is ambiguous
  2. The string $abb$ has two distinct derivations in this grammar
  3. The string $abab$ has only one rightmost derivation
  4. The language generated by the grammar is undecidable

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.

More Context-Free Grammars and Pushdown Automata questions

All Context-Free Grammars and Pushdown Automata questions →