1

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?

Michael Hardy
  • 1
geforce
  • 217

1 Answers1

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.

Brian M. Scott
  • 616,228
  • Thanks for the answer, I have one more question. Does finding a string in two different ways exactly depend on the string itself? Because I couldn't find two different ways in my string. – geforce Mar 18 '15 at 02:20
  • 1
    @geforce: Yes, it depends on the string. Some strings may have unambiguous derivations. – Brian M. Scott Mar 18 '15 at 02:21
  • Ok, is there a certain strategy or procedure to find a string that has ambiguous derivations? Is there something you look for that leads you to this? – geforce Mar 18 '15 at 02:25
  • 1
    Let me see if I can add to my answer some indication of my thought processes. – Brian M. Scott Mar 18 '15 at 02:26
  • Thanks for the explanation I will review it in more detail to understand it better. This will definitely help me out, appreciate it. – geforce Mar 18 '15 at 02:57
  • @geforce: You’re welcome; glad to help. – Brian M. Scott Mar 18 '15 at 02:58