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?

  • $\begingroup$ 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. $\endgroup$ – 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.

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

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.