Consider the following context-free grammar (CFG), where S is the start…

Concept: A grammar is ambiguous for a string w if w has two or more distinct parse trees (equivalently, two or more distinct leftmost derivations). For a grammar of the form X → XX | t, where t is one fixed terminal string, every derivation tree is a full binary tree whose leaves are all copies of t; the number of distinct tree shapes with n leaves equals the Catalan number Cn−1. So the grammar is ambiguous exactly for the values of n where Cn−1 > 1.

Application: In S → SS | xy, every string in L(G) is n concatenated copies of "xy" for some n ≥ 1, giving length 2n. Counting distinct tree shapes for small n:

1. n = 1 copy (length 2): only the direct production S → xy is used, so there is exactly 1 tree shape — C0 = 1.

2. n = 2 copies (length 4): S → SS forces one split into S → xy and S → xy; there is exactly 1 tree shape — C1 = 1.

3. n = 3 copies (length 6): S → SS can split the three copies as (1 + 2) or (2 + 1), giving 2 distinct tree shapes — C2 = 2 > 1, so this is the first ambiguous case.

Cross-check: Write out both length-6 trees explicitly for the string "xyxyxy":

• Split (1 + 2): S → S S, left S → xy, right S → S S → xy, xy.

• Split (2 + 1): S → S S, left S → S S → xy, xy, right S → xy.

Both derivations yield the same string "xyxyxy" from two different tree shapes, confirming ambiguity at length 6; the shorter strings of length 2 and 4 each admit only one possible split, so they are not ambiguous.

Therefore, the shortest string generated by the grammar that is ambiguous has length 6.