Consider the following two grammars: G1: S → AB | C G2: S → PQ | QP | R A → xA…

Answer: Both the statement that "G2 is ambiguous but its language is unambiguous" and the statement that "both G1 and G2 are ambiguous" are true. G1 and G2 (as given) are ambiguous grammars; however, the language generated by G2 can be given by an unambiguous grammar.

Proof that G1 is ambiguous:

1. Derivation 1 (using S → AB): S ⇒ AB ⇒ (A ⇒ D ⇒ x) B ⇒ x B ⇒ x (since B ⇒ ε). Resulting string: "x".

2. Derivation 2 (using S → C): S ⇒ C ⇒ x A ⇒ x (since A ⇒ ε). Resulting string: "x".

These are two different parse trees producing the same terminal string "x", so G1 is ambiguous.

Proof that G2 is ambiguous:

1. Using S → PQ: if P ⇒* ε and Q ⇒* ε then S ⇒ PQ ⇒ ε.

2. Using S → QP: if Q ⇒* ε and P ⇒* ε then S ⇒ QP ⇒ ε.

3. Also S → R → Q ⇒* ε gives another derivation of ε. Thus the empty string has multiple distinct parse trees in G2, so G2 is ambiguous.

Despite this, the language generated by G2 is not inherently ambiguous. We can give an alternative unambiguous grammar that generates the same language by choosing the start production according to the first terminal (m, r, or empty). One convenient unambiguous grammar is:

• Nonterminals: S, Empty, M_any, M_pos, N_any, N_pos

• Productions:

  S → Empty | M_pos N_any | N_pos M_any

  Empty → ε

  M_any → m M_any n | ε (generates m^k n^k, k ≥ 0)

  M_pos → m M_any n (generates m^i n^i, i ≥ 1)

  N_any → r N_any s | ε (generates r^k s^k, k ≥ 0)

  N_pos → r N_any s (generates r^j s^j, j ≥ 1)

Why this grammar is unambiguous: the first terminal of a string (if any) determines which S-production must have been used. If the string starts with m it must come from M_pos N_any; if it starts with r it must come from N_pos M_any; if it is empty it comes only from Empty. No two different S-productions can generate the same nonempty string because they produce different orders of m^i n^i and r^j s^j or require different nonzero counts. Thus every string has exactly one leftmost derivation in this grammar.

Summary: G1 is ambiguous (example string "x"). G2 (as written) is ambiguous (example: ε has multiple parses), but the language of G2 admits the unambiguous grammar above, so the language itself is not inherently ambiguous.