# Help me find the ambiguity in this grammar

I've been sitting on this for 20+ minutes and can't seem to generate a string that is ambiguous. Can anyone help me? The grammar is:

$$S \xrightarrow{} SS \mid T$$ $$T \xrightarrow{} aTb \mid ab$$

Strings I have attempted to generate and failed are:

1. abab
2. abababab
3. aabbab
4. abaabb

And none of these seem to be generated by more than one left-most derivation. Can anyone come up with one that works?

• All the ambiguity is in the first rule $S\to SS$. Your string 2 is 5 times ambiguous, it has 5 different leftmost derivations, i.e. 5 different parse-tree. – babou Dec 7 '14 at 7:54

$$S \xrightarrow{} SS \xrightarrow{} SSS \xrightarrow{} TSS \xrightarrow{} abSS \xrightarrow{} abTS \xrightarrow{} ababS \xrightarrow{} ababT \xrightarrow{} ababab$$ $$S \xrightarrow{} SS \xrightarrow{} TS \xrightarrow{} abS \xrightarrow{} abSS \xrightarrow{} abTS \xrightarrow{} ababS \xrightarrow{} ababT \xrightarrow{} ababab$$

As @babou mentions in a comment, a production of the form

$$N \xrightarrow{} NN \mid X$$

is always ambiguous, since it can generate any binary tree with the right number of leaves as a parse tree. Compare it with:

$$N \xrightarrow{} XN \mid X$$ or $$N \xrightarrow{} NX \mid X$$

which only generate right- and left-biased binary trees, respectively.

As a point of interest, the number of binary trees with $k$ leaves is $C_{k-1}$, the Catalan number of index $k-1$. So $TTT$ can be produced in two ways (as above) and $TTTT$ in five ways.

• Wow! I missed it by one set of abs. How embarrassing. Thanks for pointing this out. – Joe Dec 7 '14 at 7:15
• @Joe You did not miss it, you failed to see it, as I said in my first comment above, since you tried $abababab$. – babou Dec 7 '14 at 22:04