Consider the following grammar where π is the start symbol, and π and π areβ¦
2026
Consider the following grammar where π is the start symbol, and π and π are terminal symbols.
πβππππ β£ ππ β£ Ο΅
Which of the following statements is/are true?
- A.
The grammar is ambiguous
- B.
The string πππ has two distinct derivations in this grammar
- C.
The string ππππ has only one rightmost derivation
- D.
The language generated by the grammar is undecidable
Attempted by 17 students.
Show answer & explanation
Correct answer: A, B, C
The grammar S β aSbS | bS | Ξ΅ generates a Context-Free Language. To check for ambiguity, consider the string 'abb'. It admits two distinct derivations: S β aSbS β abS bS β abb and another structural variation, confirming the grammar is ambiguous (Options 0 and 1). For string 'abab', the derivation structure forces a unique rightmost path, validating Option 2. Since all Context-Free Languages are decidable, the claim regarding undecidability is false.