Consider the following two grammars: G1 : S → SbS | a G2 : S → aB | ab, A → AB…

Concept

A context-free grammar is ambiguous if there exists at least one string in its language that has two or more distinct parse trees (equivalently, two distinct leftmost derivations). It is enough to exhibit a single such string; the rest of the grammar need not be examined once one ambiguous string is found.

Application

Grammar G1 : S → SbS | a. Take the string “ababa”. The middle S → SbS can be expanded in two ways:

1. Left-grouping: S ⇒ SbS ⇒ (SbS)bS ⇒ (a b a) b a, i.e. the outer “b” joins a left subtree (a b a) with a.

2. Right-grouping: S ⇒ SbS ⇒ a b (SbS) ⇒ a b (a b a), i.e. the outer “b” joins a with a right subtree (a b a).

Both yield the same string “ababa” but build different parse trees, so G1 is ambiguous.

Grammar G2 : S → aB | ab, A → AB | a, B → ABb | b. Take the string “ab”:

1. S ⇒ ab, using the single production S → ab.

2. S ⇒ aB ⇒ ab, using S → aB and then B → b.

These are two different derivations (and two different parse trees) of the same string “ab”, so G2 is ambiguous. Note this argument needs only S → aB | ab and B → b; the production for A does not affect this string.

Cross-check

Apply the definition back to each result: a single string with two parse trees was produced for G1 (“ababa”) and for G2 (“ab”). Since each grammar has at least one ambiguous string, both grammars are ambiguous — matching the option “Both G1 and G2 are ambiguous.”