Consider the following grammar where S is the start symbol, and a and b are terminal symbols. S aSbS bS Which of the following statements is/are true?

The string abb has two distinct derivations in this grammar

The string abab has only one rightmost derivation

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

GATE CSE 2026 Session 1 Q25: Ambiguity of S → aSbS | bS | ε

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?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: A, B, C (official GATE 2026 final answer key)

Concept used: A grammar is ambiguous if some string has two parse trees; membership in a CFL is always decidable.

First step: Parse $abb$ from $S \to aSbS$ : the extra $b$ can come from the first $S$ (via $bS$ ) or from the second $S$ .

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2026 Session 1 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key