Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The BNF is defined as follows:

<S> -> <S>a<S>a<S> | b

This is my review question for a quiz, and according to my teacher, this grammar is ambiguous. However, I realized this grammar is not.
For example, given a sentence:

babababab

There are three ways to generate this sentence depending on which <S> we use, but its parse-tree is unique.
Am I right in this case? Any feedback would be greatly appreciated.

Thanks,
Chan

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

Starting with your formal grammar consisting of one production rule, $S \to SaSaS | b$, I'm going to modify it be adding parenthesis to demonstrate the the possible ways of generating your objective string $babababab$.

Let the demonstrative formal grammar be given by the production rule $S \to (S)a(S)a(S) | b$.

Starting with $(S)a(S)a(S)$ we can produce the following strings: $((b)a(b)a(b))a(b)a(b)$, $(b)a((b)a(b)a(b))a(b)$ and $(b)a(b)a((b)a(b)a(b))$.

If we remove the paratheses, (effectively performing the same set of operations using your formal grammar), then we arrive at your objective string $babababab$.

By definition, any formal grammar that yields the same string by applying the production rules in multiple ways, is ambiguous.

Therefore, your formal grammar is ambiguous. (the demonstrative formal grammar is not, since each string is unique.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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