Consider the grammar G with the following production: S → S + S | a Which…
Consider the grammar G with the following production:
S → S + S | a
Which statement is correct?
Answer: D. Grammar G is ambiguous. — ConceptA context-free grammar is ambiguous if at least one generated string has more than one distinct parse tree. Each parse tree corresponds to a distinct…
- A.
Every string generated by G has exactly one parse tree.
- B.
The string a+a has two distinct leftmost derivations.
- C.
The string a+a+a has exactly one parse tree.
- D.
Grammar G is ambiguous.
Attempted by 144 students.
Show answer & explanation
Correct answer: D
Concept
A context-free grammar is ambiguous if at least one generated string has more than one distinct parse tree.
Each parse tree corresponds to a distinct leftmost derivation, so two leftmost derivations for the same string establish ambiguity.
Application
For the grouping (a+a)+a, a leftmost derivation is S ⇒ S+S ⇒ S+S+S ⇒ a+S+S ⇒ a+a+S ⇒ a+a+a.
For the grouping a+(a+a), another leftmost derivation is S ⇒ S+S ⇒ a+S ⇒ a+S+S ⇒ a+a+S ⇒ a+a+a.
The same string a+a+a therefore has two distinct parse trees.
Cross-check and contrast
For a+a, there is one parse tree and one leftmost derivation.
For a+a+a, the two groupings (a+a)+a and a+(a+a) give two parse trees, not one.
The claim that every generated string has exactly one parse tree is contradicted by a+a+a.
Therefore, Grammar G is ambiguous.