Consider the following grammar where 𝑆 is the start symbol, and 𝑎 and 𝑏 are…

SOLUTION:

OPTION A) TRUE. The grammar is ambiguous.

A grammar is ambiguous if and only if there exists at least one string in L(G) for which the grammar produces more than one parse tree.

String abb ∈ L(G) and G produces more than one parse tree for abb:

OPTION B) TRUE. The string abb has two distinct derivations in this grammar.

1st derivation:

S ⇒ aSbS
⇒ abS
⇒ abbS
⇒ abb

2nd derivation:

S ⇒ aSbS
⇒ abSbS
⇒ abbS
⇒ abb

Note that the question is not asking for rightmost (or leftmost) derivations. It is just asking about derivations. There are more than 2 derivations of the string abb, but the question is asking for the existence of at least two derivations.

OPTION C) TRUE. The string abab has only one rightmost derivation.

S ⇒rmd aSbS
⇒rmd aSbaSbS
⇒rmd aSbaSb
⇒rmd aSbab
⇒rmd abab

At each step, the next terminal forces a unique production choice, so no alternative rightmost derivation exists.

This fact can also be seen using the parse tree. There is only 1 parse tree that yields the string abab. Therefore, only 1 rightmost derivation exists. For any CFG, the number of rightmost derivations is the same as the number of parse trees for a given string.

OPTION D) False. The language generated by the grammar is undecidable.

This is incorrect. The given grammar is a context-free grammar (CFG), and every language generated by a CFG is a context-free language. Membership testing for context-free languages is decidable.

Therefore, the language generated by the grammar is decidable, not undecidable.