GATE CS 2026 Set 1 Q.25: Context-Free Grammars, Pushdown Automata and CFLs

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

S \rightarrow aSbS \mid bS \mid \epsilon

Which of the following statements is/are true?

The grammar is ambiguous

The string $abb$ has two distinct derivations in this grammar

The string $abab$ has only one rightmost derivation

The language generated by the grammar is undecidable

Official answer and solution

Solution

Test derivations of $abb$ and $abab$ under the given CFG and recall that every CFL is decidable.

Options (A) and (B) are true: The string $abb$ $abb$ has two distinct leftmost derivations (and two distinct parse trees):
- $S \Rightarrow aSbS \Rightarrow abS \Rightarrow abbS \Rightarrow abb$ (where the first $S$ derives $\epsilon$ and the second $S$ derives $b$ via $bS \Rightarrow b$ )
- $S \Rightarrow aSbS \Rightarrow abSbS \Rightarrow abbS \Rightarrow abb$ (where the first $S$ derives $b$ via $bS \Rightarrow b$ and the second $S$ derives $\epsilon$ )
  Hence $abb$ has two distinct derivations and the grammar is ambiguous.
Option (C) is true: Every application of $S \rightarrow aSbS$ introduces one $a$ and one $b$ , while $S \rightarrow bS$ introduces an extra $b$ . Since $abab$ has two $a$ 's and two $b$ 's, the production $S \rightarrow bS$ can never be used in deriving $abab$ . Restricting to $S \rightarrow aSbS \mid \epsilon$ (the unambiguous Dyck grammar), $abab$ has a unique parse tree and therefore only one rightmost derivation: $S \Rightarrow_{\text{rm}} aSbS \Rightarrow_{\text{rm}} aSbaSbS \Rightarrow_{\text{rm}} aSbaSb \Rightarrow_{\text{rm}} aSbab \Rightarrow_{\text{rm}} abab$
Option (D) is false: Every context-free language is decidable.

Final answer

Options (A), (B), (C)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 25 of 65
Section: Computer Science and Information Technology

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.