0
$\begingroup$

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:

enter image description here

Right most derivation tree:

enter image description here

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

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