A grammar G is ambiguous. Which of the following statements are true?

Definition: A context-free grammar G is called ambiguous if there exists at least one string in L(G) that has two distinct parse trees (equivalently, two distinct derivations or two distinct leftmost/rightmost derivations).

• Why the statement "Every string in L(G) has multiple derivations" is false: This claim is too strong. Ambiguity only requires existence of at least one string with multiple derivations. For example, consider the grammar with productions S -> S S | a. The string "a" has a unique derivation, while the string "aa" can be derived in more than one way, so the grammar is ambiguous but not every string has multiple derivations.

• Why the statement "Every string in L(G) has multiple parse trees" is false: This is the same type of overreach as the previous item. Parse trees and derivations correspond, but ambiguity only guarantees at least one string with multiple parse trees, not all strings.

• Why the statement "At least one string in L(G) has multiple derivations" is true: This is exactly the definition of an ambiguous grammar: existence of at least one string with two distinct derivations or parse trees.

• Why the statement "At least one string in L(G) has multiple leftmost derivations (LMDs)" is true: Each parse tree corresponds to a unique leftmost derivation. So if a string has two different parse trees, it also has two different leftmost derivations.

Correct statements:

• At least one string in L(G) has multiple derivations.

• At least one string in L(G) has multiple leftmost derivations (LMDs).