Consider the following two grammars G₁ S → SbS / a G₂ S → aB / ab A → AB / a B…
2018
Consider the following two grammars
G₁
S → SbS / a
G₂
S → aB / ab
A → AB / a
B → Abb / b
Which of the following option is correct?
- A.
Only G₁ is ambiguous
- B.
Only G₂ is ambiguous
- C.
Both G₁ and G₂ are ambiguous
- D.
Both G₁ and G₂ are not ambiguous
Attempted by 71 students.
Show answer & explanation
Correct answer: C
Grammar G1 defined by S → SbS / a is ambiguous. The string 'aba' has two distinct parse trees: one where the first S derives 'a' and the second S derives 'a', and another where the middle structure differs. This ambiguity arises because the production allows recursive expansion in multiple ways for the same string.