GATE CS 2026 Set 1 Q15 — Context-free Grammars and Push-down Automata

Let us analyze each option step-by-step:

• Options A and B: A grammar is ambiguous if there exists a string with more than one distinct leftmost derivation (or parse tree). Let us find the leftmost derivations (LMD) for the string $abb$:
  1. LMD 1: $S \Rightarrow aSbS \Rightarrow a(bS)bS \Rightarrow abSbS \Rightarrow ab(\epsilon)bS \Rightarrow abb(\epsilon) = abb$
  2. LMD 2: $S \Rightarrow aSbS \Rightarrow a(\epsilon)bS \Rightarrow abS \Rightarrow ab(bS) \Rightarrow abb(\epsilon) = abb$
  Since $abb$ has exactly two distinct derivations, Option A and Option B are both TRUE.
• Option C: To generate the string $abab$, the derivation must start with $S \rightarrow aSbS$. To match the prefix $a$ and the subsequent $b$, the only valid partition is for the first $S$ to derive $\epsilon$ and the second $S$ to derive $ab$ (since any other choice leads to too many terminals or mismatched prefixes).
  The unique rightmost derivation (RMD) is: $$S \Rightarrow aSbS \Rightarrow aSbaSbS \Rightarrow aSbaSb \Rightarrow aSbab \Rightarrow abab$$ Since there is only one rightmost derivation for $abab$, Option C is TRUE.
• Option D: The given grammar is a Context-Free Grammar (CFG). The language generated by any CFG is a Context-Free Language (CFL), which is always decidable. Thus, Option D is FALSE.