Computer Sciences > GATE 2026 SET-1 > Context Free Grammar
Consider the following grammar where 𝑆 is the start symbol, and 𝑎 and 𝑏 are terminal symbols.

S → aSbS | bS | ε

w which of the following statements is/are true?
A
The string 𝑎𝑏𝑎𝑏 has only one rightmost derivation.
B
The language generated by the grammar is undecidable.
C
The grammar is ambiguous.
D
The string 𝑎𝑏𝑏 has two distinct derivations in this grammar.

Correct : a,c,d

Option A - True.
Rightmost derivation of "abab":
S → aSbS → aSb(bS) → aSb(b) → a(aSbS)b(b) → a(aSb)bb → a(a)bbb — this does not work.
Correct rightmost derivation:
S → aSbS → aSb(ε) → aSb → a(aSbS)b → a(aSb(ε))b → a(aSb)b → a(a(ε)b)b = aabb — not "abab"
S → aSbS → aSb(bS) → aSb(b(ε)) → aSbb → not "abab"
S → aSbS → a(ε)bS → abS → ab(aSbS) → ab(a(ε)b(ε)) → abab
Only one such rightmost derivation exists for "abab". True.
Option B - False.
The language generated by a context free grammar is always decidable (it is recursively enumerable and decidable using CYK algorithm). False.
Option C - True.
A grammar is ambiguous if any string has more than one parse tree (or leftmost/rightmost derivation).
For "abb", two derivations exist (shown in Option D below), so the grammar is ambiguous. True.
Option D - True.
Derivation 1 of "abb":
S → aSbS → a(ε)bS → abS → ab(bS) → ab(b(ε)) → abb ✓
Derivation 2 of "abb":
S → bS → b(aSbS) → b(a(ε)b(ε)) — gives "bab", not "abb"
S → aSbS → a(ε)b(bS) → ab(b(ε)) → abb ✓ (same path)
S → aSbS → a(bS)bS → a(b(ε))b(ε) → abb ✓ (different parse tree)
Two distinct parse trees exist for "abb". True.
The correct statements are A, C and D

Similar Questions

Consider the following context free grammar:S → abaABAbbaA → aaBBAb | bBabaaB → aBb | abL(G) is the language generated by the grammar. For a stri...
#1494 MSQ
A palindrome is a word that reads the same forwards and backwards. In a game of words, a player has the following two plates painted with letters. From...
#1 MCQ
Which number does not belong in the series below? 2, 5, 10, 17, 26, 37, 50, 64
#4 MCQ

Related Topics

GATE 2026 Computer Science CSE Set 1 Question 5 Theory of Computation Context Free Grammar CFG Ambiguous Grammar Rightmost Derivation Leftmost Derivation Parse Tree Formal Languages Automata Theory Pushdown Automata MSQ Multiple Select Question 2 Marks

Unique Visitor Count

Total Unique Visitors

Loading......