next up previous
Next: About this document ... Up: Elements of Answers for Exercise Previous: Show that the language L

Show that G is ambiguous.

The word w = $ \bf a$ $ \bf\mid$ $ \bf b$ $ \bf a$ has the following two left most derivations

R $\displaystyle \Rightarrow$ RR
  $\displaystyle \Rightarrow$ R $\displaystyle \bf\mid$ RR
  $\displaystyle \Rightarrow$ $\displaystyle \bf a$ $\displaystyle \bf\mid$ RR
  $\displaystyle \Rightarrow$ $\displaystyle \bf a$ $\displaystyle \bf\mid$ $\displaystyle \bf b$R
  $\displaystyle \Rightarrow$ $\displaystyle \bf a$ $\displaystyle \bf\mid$ $\displaystyle \bf b$$\displaystyle \bf a$
   

R $\displaystyle \Rightarrow$ R $\displaystyle \bf\mid$ R
  $\displaystyle \Rightarrow$ $\displaystyle \bf a$ $\displaystyle \bf\mid$ R
  $\displaystyle \Rightarrow$ $\displaystyle \bf a$ $\displaystyle \bf\mid$ RR
  $\displaystyle \Rightarrow$ $\displaystyle \bf a$ $\displaystyle \bf\mid$ $\displaystyle \bf b$R
  $\displaystyle \Rightarrow$ $\displaystyle \bf a$ $\displaystyle \bf\mid$ $\displaystyle \bf b$$\displaystyle \bf a$
   

This shows that G is ambiguous.


next up previous
Next: About this document ... Up: Elements of Answers for Exercise Previous: Show that the language L
Marc Moreno Maza
2004-12-01