Given the grammar with productions: \begin{align} S \rightarrow aSb \mid SS \mid \lambda\\ \end{align} I would like to show that it is ambiguous. As I understand it, if you can show that some string can be produced with these rules through more than one leftmost or rightmost derivation, then the grammar is ambiguous.

As such, I tried to get two ways that derive the string "ab" using leftmost derivations: \begin{align} S \Rightarrow aSb \Rightarrow a\lambda b \Rightarrow ab\\ S \Rightarrow SS \Rightarrow aSbS \Rightarrow a\lambda b\lambda \Rightarrow ab \end{align}

Because there are two different leftmost derivations of the same string "ab", the grammar must be ambiguous.

However, my professor indicated to me that my answer is wrong, and I did not use all the production rules. I thought I had, though. He told me I could instead derive the string "aabb" to prove the ambiguity, but I don't know what would make that fundamentally different.

Can anyone help explain why this relatively simple string "ab" doesn't work, at least as I attempted to prove it? Thanks!


2 Answers 2


I believe your professor is wrong. You exhibited two leftmost derivations, which is all that is required to show a grammar is ambiguous. Although, one small thing: $S \Rightarrow SS \Rightarrow aSbS \Rightarrow a\lambda b\lambda \Rightarrow ab$ should have another rule as you have followed two rules at once, $S \Rightarrow SS \Rightarrow aSbS \Rightarrow abS \Rightarrow ab$ (in other words, you eliminated two $S$ variables at once). Also, as you have mentioned, you actually did use every production rule.


if the ambiguity was the problem, then your solution is completely correct, showing 1 example, where derivation isn't unique is enough to prove that grammar is ambiguous in this case.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.