1
$\begingroup$

The BNF is defined as follows:

 -> aa | 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 we use, but its parse-tree is unique.
Am I right in this case? Any feedback would be greatly appreciated.

Thanks,
Chan

1 Answers 1

3

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.)