A CFG is AMBIGUOUS if
Ait has more than one variable
Bthe grammar has rules but no terminals
Ca string in $L(G)$ has two or more distinct parse trees
Dthe grammar accepts the empty string
Answer & Solution
Correct answer: C. a string in $L(G)$ has two or more distinct parse trees
1. Ambiguity in a CFG: a string in $L(G)$ has multiple structurally distinct parse trees.
2. Classic example: arithmetic expressions. Grammar $E \to E + E \mid E \cdot E \mid \text{id}$. The string '$id + id \cdot id$' has TWO parse trees:
- $(id + id) \cdot id$ (top-level $\cdot$, left subtree is sum)
- $id + (id \cdot id)$ (top-level +, right subtree is product)
3. Each parse tree assigns a different MEANING, so ambiguity is a SEMANTIC PROBLEM for parsers (which interpretation should the compiler choose?).
4. SOLUTION: rewrite grammars to enforce precedence, e.g. $E \to E + T \mid T$; $T \to T \cdot F \mid F$; $F \to id$. This makes the grammar unambiguous.
5. Other options don't define ambiguity.
_Source: Jeff Erickson, "Models of Computation", §5.7 (Ambiguity in CFGs)._
Related questions
Which class of grammars generates ALL recursively enumerable languages?What is a LEFTMOST DERIVATION?Which of the following languages is CONTEXT-FREE?Consider the grammar $S \to (S) \mid SS \mid \varepsilon$. The language generated isEvery regular language is also context-free. The PROOF construction isThe CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ isA LEFT-RECURSIVE rule in a CFG has the form $A \to A\alpha$ for some non-empty $\alpha$. WContext-free languages are CLOSED under which of the following operations?