When is a grammar ambiguous or When is a grammar not ambiguous?

Question

I was looking at an example of grammar from the website: grammer example

which is as follows:

S → aB / bA

S → aS / bAA / a

B → bS / aBB / b

I believe they forgot to write: A -> a

Next, we are going to derive the string: aaabbabbba

I did it by myself and found the following:

Left derivation:

S -> aB

-> aaBB

-> aaaBBB

-> aaabBB

-> aaabbB

-> aaabbaBB

-> aaabbabB

-> aaabbabbS

-> aaabbabbbA

-> aaabbabbba

Right Most Derivation:

S -> aB

-> aaBB

-> aaBbS

-> aaBbbA

-> aaBbba

-> aaaBBbba

-> aaaBbbba

-> aaabSbbba

-> aaabbAbbba

-> aaabbabbba

And the left most derivation tree:

Right most derivation tree:

Now, if the website says the grammer is "unambiguous" then shouldn't the parse trees of left most derivation and right most derivation be the same? am i correct or is the website correct?

Also, when is a grammer ambiguous? I feel it is when:

(1) It has more than 1 left most derivation tree for the same string

(2) It has more than 1 right most derivation tree for the same string

(3) It has different left most and right most derivation tree for the same string

In the above rules i mean the shape of the parse / derivation tree, not the actual substitution

Am i correct?

Answer 1

That grammar as presented (with the addition of the production $A\to a$) is certainly ambiguous, regardless of what the site you copied it from says. Your work demonstrates that, and it can easily be verified using a parser generator or CFG analyzer. (See below for what they probably meant.)

A grammar is ambiguous if it has more than one leftmost derivations for a sentence. That's equivalent to saying that it had more than one rightmost derivation for the same sentence because the is a one-to-one correspondence between leftmost and rightmost derivations. Every leftmost derivation can be mechanically transformed into a unique rightmost derivation, and vice versa. (And that transformation preserves parse trees.)

You might find it useful to do that for your derivations; you will see that you can find two leftmost derivations and two corresponding rightmost derivations. (And two parse trees, which you already drew.)

I think you did not correctly guess the typo in that webpage. It's not that one production for $A$ is missing. Rather, the second line of the grammar should have read: $$A\to a S \mid b A A \mid a$$ instead of $S\to…$. You might also want to try using that version of the grammar.