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

Explanation

Consider the string $abb$:
- Derivation 1: $S \Rightarrow aSbS \Rightarrow a\epsilon bS \Rightarrow ab(bS) \Rightarrow abb\epsilon = abb$.
- Derivation 2: $S \Rightarrow aSbS \Rightarrow a(bS)bS \Rightarrow ab\epsilon b\epsilon = abb$.
Since there are two distinct leftmost derivations (and two distinct parse trees) for the string $abb$, the grammar is ambiguous. This confirms statement (A) is true and statement (B) is true.
- Statement (C) is false because $abab$ also admits multiple rightmost derivations due to the ambiguity of the grammar.
- Statement (D) is false because any language generated by a context-free grammar is context-free, and context-free languages are decidable.

Therefore, options (A) and (B) are true.