How do you show that a cfg is ambiguous?

Question

Do we just need to show that we can get a certain string more than in 1 way?

S > SSaS|SS|a|epsilon

Ex: S > SSaS > aa

S > SS > aa

Answer 1

Do we just need to show that we can get a certain string more than in 1 way?

Yes, that is exactly what you need to do. Just be certain that you specify which string you derived in plural ways, and show the derivations. You have now just one derivation, which I think is problematic:

Ex: S > SSaS > aa S > SS > aa

The grammar you've given is indeed ambiguous - but you'll need at least two derivations for the same string to show this, of course.

Answer 2

The grammar is indeed ambiguous, and the two derivations you provide do the job. However, your derivations do skip some steps; the full derivations should be:

S > SSaS > SSaa > Saa > aa

and

S > SS > Sa > aa

Thus, because the string $aa$ can be derived in two ways (in fact, there are infinitely many more ways to derive it), the grammar is ambiguous.

Answer 3

Some tips:

1. All CFG without useless symbols and with left and rigth recursion for the same symbol, is ambiguous. In general:

   A -> Az | xA | y
   (z, x, y are strings of 0 or more symbols or terminals)

   Let s probe it:

   there is a leftmost derivation A > Az > xAz ... and another A > xA > xAz ...

   to reach the same string.

   In your case, S -> SS | ... is ambiguous, and S -> SSaS | ... too.

2. To probe ambiguity, you must find 2 Leftmost Derivations for the same string (or 2 rightmost derivations, or 2 derivation trees). It s not enough to find 2 any derivations... it must be both leftmost or both rigthmost.