Proving ambiguity of this Context Free Grammar

Question

I ran into this exercise problem from Introduction To The Theory Of Computation by Sipser. Given a context free grammar:

$ S \rightarrow SS \ | \ T \\ T \rightarrow aTb \ | \ ab $

I have to show that the grammar is ambiguous. So I have to find at least two leftmost derivation of a string. I have tried a lot but have failed to come up with a counter-example. I think T describes the following grammar:

$ L = {\{a^nb^n} \ | \ n > 0 \} $

But if I take $SS$, it is equivalent to taking $TT$, then it generates the strings like $ a^n b^n a^nb^n $, which is entirely different from L. So how can I come up with a string that has two leftmost derivation in this grammar. Any sort of help would be appreciated!

Below is the picture from the exercise.

Answer 1

The string $ababab$ has two different parse trees. In one of them the first two $ab$'s are grouped together, and in the other one, the last two $ab$'s are grouped together.

Stated differently, one parse tree corresponds to a derivation $S \Rightarrow SS \Rightarrow^* ababS \Rightarrow^* ababab$, and the other one to a derivation $S \Rightarrow SS \Rightarrow^* Sabab \Rightarrow^* ababab$. If you draw the parse trees for both derivations, you'll see that you get different parse trees.

Finally, here are actual two different leftmost derivations of $ababab$:

1. $S \Rightarrow SS \Rightarrow SSS \Rightarrow TSS \Rightarrow abSS \Rightarrow abTS \Rightarrow ababS \Rightarrow ababT \Rightarrow ababab$.
2. $S \Rightarrow SS \Rightarrow TS \Rightarrow abS \Rightarrow abSS \Rightarrow abTS \Rightarrow ababS \Rightarrow ababT \Rightarrow ababab$.

As an aside, an equivalent unambiguous grammar replaces the production $S \to SS$ by the production $S \to ST$ (or by the production $S \to TS$).