Given the following grammars G₁ S → AB / aaB A → aA / ε B → bB / ε G₂ S → A /…
2015
Given the following grammars
G₁
S → AB / aaB
A → aA / ε
B → bB / ε
G₂
S → A / B
A → aAb / ab
B → abB / ε
- A.
G₁ is ambiguous and G₂ is unambiguous grammars
- B.
G₁ is unambiguous and G₂ is ambiguous grammars
- C.
Both G₁ and G₂ are ambiguous grammars
- D.
Both G₁ and G₂ are unambiguous grammars
Attempted by 59 students.
Show answer & explanation
Correct answer: C
To determine ambiguity, we check if any string has multiple distinct parse trees.
For G₁, the string aa can be derived via S → AB ⇒ aA B ⇒ aaB ⇒ aa or directly via S → aaB ⇒ aa. This confirms G₁ is ambiguous.
For G₂, the string ab can be derived via S → A ⇒ ab or via S → B ⇒ abB ⇒ ab. Since both grammars allow multiple parse trees, they are both ambiguous.
A video solution is available for this question — log in and enroll to watch it.