2
$\begingroup$

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.

enter image description here

$\endgroup$
1
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.