# Inherent ambiguity of the language $L_2 = \{a^nb^mc^m \;|\; m,n \geq 1\}\cup \{a^nb^nc^m \;|\; m,n \geq 1\}$

I went through a question asking me to choose the inherently ambiguous language among a set of options.

$$L_1 = \{a^nb^mc^md^n \;|\; m,n \geq 1\}\cup \{a^nb^nc^md^m \;|\; m,n \geq 1\}$$ $$and$$ $$L_2 = \{a^nb^mc^m \;|\; m,n \geq 1\}\cup \{a^nb^nc^m \;|\; m,n \geq 1\}$$

The solution said that $L_1$ is ambiguous while $L_2$ isn't. It generated the following grammar for $L_1$

$S \rightarrow S_1\;|\;S_2$

$S_1 \rightarrow AB$

$A \rightarrow aAb\;|\;ab$

$B \rightarrow cBd\;|\;cd$

$S_2 \rightarrow aS_2d\;|\;aCd$

$C \rightarrow bCc\;|\;bc$

Now for the string abcd, it will generate two parse trees; so it is ambiguous.

But a similar grammar can be created for $L_2$ too

$S \rightarrow S_1|S_2$

$S_1 \rightarrow Ac$

$A \rightarrow aAb\;|\;\epsilon$

$S_2 \rightarrow aB$

$B \rightarrow bBc\;|\;\epsilon$

And it will also generate two parse trees for abc. Why isn't it ambiguous then?

If you need, $L_2$ can be written as $\{a^nb^pc^m\;|\; n=p \;\; or \;\; m=p\}$

-
Just a quick comment: a grammar can be ambiguous or not; A languages cannot be ambiguous, but it can be inherently ambiguous which means that any grammar for that language is ambiguous. – Ran G. Nov 9 '12 at 6:06
$L_1$ is indeed inherently ambiguous, and I assume you ask to show that $L_2$ is not, that is, to show a non-ambiguous grammar for $L_2$. You should edit the question accordingly, if so. – Ran G. Nov 9 '12 at 6:09
I think $L_2$ is ambiguous too. But the solution said it isn't. I want to know "how". – Shashwat Nov 9 '12 at 6:17
See here for a technique that might be useful here. – Raphael Nov 9 '12 at 7:33

The question is wrong. The second language is also inherently ambiguous. The usual way this is proved is as follows. Suppose $L_2$ had an unambiguous grammar. Let $p$ be the constant promised by Ogden's lemma, and consider the word $a^{p!+p} b^p c^p$. Mark the positions of $b^p c^p$ and apply Ogden's lemma to pump this word to the word $a^{p!+p} b^{p!+p} c^{p!+p}$ (Ogden's lemma allows us to pump some $b^q c^q$ for $q\leq p$, and $q|p!$ since $q \leq p$.) Similarly, we can get the same word by pumping $a^p b^p c^{p!+p}$. The two parse trees are different since in the first one most of the $b$s are "closely related" (in terms of least common ancestor) to $c$s, and in the second one it is the other way around.
As a note, language $L_2$ in fact is mentioned as an example in Ogden's original 1968 paper "A helpful result for proving inherent ambiguity". The result on that language itself is attribute to Ginsburg, but probably obtained using horrible adhoc methods. – Hendrik Jan Nov 9 '12 at 23:44
You're quite right to be dubious, $L_{2}$ is also inherently ambiguous. It's even been used as a "prototype of an inherently ambiguous language" by Flajolet (right at the start of section 2).