1

Equivalent unambiguous grammar: \begin{align} S &\rightarrow ABA|AB|BA|A|B \\ A &\rightarrow aA | a \\ B &\rightarrow aB|b \end{align}

an unambiguous language has only one parse tree, but there are two parse trees for the grammar above:

$ABA > ABa > aBa > aba$

$ABA > aBA > abA > aba$

Cookie
  • 13,532
george
  • 11
  • 2
    Those aren't parse trees. They are two derivations(?) corresponding to the same parse tree. Try drawing the actual tree and you'll see. –  Apr 24 '14 at 03:10

1 Answers1

1

It's not about the grammar, it's about the strings. If you see aaba there's only one way to parse it: aa is A, b is B, a is A, and the aaba = ABA is S.

Charles
  • 32,122