Show that this CFG is ambiguous

Question

Let $G=\langle V,T,P,S\rangle$ be the grammar defined by the productions:

         S-> aB|bA

         A->a|aS|bAA

         B->b|bS|aBB

where $V=\{S,A,B\}$ and $T=\{a,b\}$. Show that G is ambiguous.

My Approach:

Left-most Derivation:

S => bA => baS => baaB => baabS => baabbA => baabba

Right-most Derivation:

S => bA => baS => baaB => ... (this is where I got stuck)

To show a CFG is ambiguous I need to show two different ways to obtain the same string which would be: using left-most and right-most derivation

I can't seem to do right-most derivation no matter how much I try I always end up having to do the same thing as left-most. Any suggestions?

Answer 1

$$\begin{array}{ccc} &&&&&&&&aaabSBB&\\ &&&&&&&\nearrow&&\searrow\\ S&\to&aB&\to&aaBB&\to&aaaBBB&&&&aaabaBBB\\ &&&&&&&\searrow&&\nearrow\\ &&&&&&&&aaabBB \end{array}$$

Added: The first thing that I noticed is that the grammar is symmetric in $a$ and $b$, so that it cannot matter whether I start with $S\to aB$ or with $S\to bA$; I arbitrarily chose the former. In order to get two different leftmost derivations of the same string, I probably want to get a string of several non-terminals, so I applied $B\to aBB$ a couple of times to bet $aaaBBB$. At that point I simply tried both $B\to b$ and $B\to bS$ to see what would happen, and it worked.

In fact I worked harder than necessary: I could have done the same thing from $aaBB$, getting $aabB$ and $aabSB$, each of which then yields $aabaBB$.

If I’d been cleverer, I might have noticed right away that $SB$ and $B$ both yield $aBB$ and tried deliberately to produce $SB$ and $B$ in the same environment.