Find the Ambiguous CFG.

Answer: The ambiguous grammar is S → 1S | S0 | 2.

Explanation and explicit ambiguity example:

• Two different leftmost derivations for the string 120 show ambiguity:

1. Derivation 1 (use production that adds a leading 1 first): S ⇒ 1S ⇒ 1 S0 ⇒ 1 2 0

2. Derivation 2 (use production that adds a trailing 0 first): S ⇒ S0 ⇒ 1S0 ⇒ 1 2 0

These two derivations produce the same terminal string but have different parse-tree shapes, so the grammar S → 1S | S0 | 2 is ambiguous.

Why the other grammars are unambiguous:

• Grammar S → 1S | 0S | 2: This generates strings by repeatedly prepending a 1 or 0 until the base 2 is produced (strings of the form (1|0)*2). For any final string, the sequence of prepended symbols is exactly the prefix before 2, so the derivation is unique.

• Grammar S → 1S0 | 2: This generates strings of the form 1^n 2 0^n. The number of recursive steps n is fixed by the counts of 1s and 0s in the string, so there is exactly one derivation for each string.

Conclusion: S → 1S | S0 | 2 is ambiguous (example: 120). The other two listed grammars are unambiguous.