Consider the grammars G1 and G2: G1: S → 0S0 | 1S1 | 0 | 1 | ε; G2: S → aS |…

CONCEPT

A context-free grammar is ambiguous if some generated string has two distinct parse trees, equivalently two distinct leftmost derivations.

One witness string proves ambiguity. For a grammar with nested matching symbols, uniqueness can be tested by checking whether the outer symbols force exactly one production at every stage.

APPLICATION

1. For G1, the base strings are ε, 0, and 1. Every longer generated string begins and ends with the same symbol. Outer 0s force S → 0S0, while outer 1s force S → 1S1. Removing that forced pair leaves a shorter string with the same property, so the derivation is unique recursively. Thus G1 is unambiguous.

2. For G2, the string aa has two distinct derivations. First: S ⇒ aS ⇒ aX ⇒ aa. Second: S ⇒ X ⇒ Xa ⇒ aa. Since the same string has two parse structures, G2 is ambiguous.

CROSS-CHECK

• In G1, strings such as 00 and 010 have their first production fixed by their matching outer symbols; the same check repeats on the inner substring.

• In G2, the witness aa is sufficient because its two derivations begin with different productions, S → aS and S → X.

Therefore, G1 is unambiguous and G2 is ambiguous.