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\}$

  • 7
    $\begingroup$ 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. $\endgroup$
    – Ran G.
    Nov 9, 2012 at 6:06
  • $\begingroup$ $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. $\endgroup$
    – Ran G.
    Nov 9, 2012 at 6:09
  • $\begingroup$ I think $L_2$ is ambiguous too. But the solution said it isn't. I want to know "how". $\endgroup$
    – Shashwat
    Nov 9, 2012 at 6:17
  • 3
    $\begingroup$ See here for a technique that might be useful here. $\endgroup$
    – Raphael
    Nov 9, 2012 at 7:33
  • 2
    $\begingroup$ @FatemehKarimi ambiguity is a property of the grammar, not the language. That is, some language $L$ may have two grammars: one ambiguous and the other not. If all the grammars are ambiguous then the language is said to be inherently ambiguous. $\endgroup$
    – Ran G.
    Apr 20, 2018 at 16:01

2 Answers 2


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.

  • 1
    $\begingroup$ See the following presentation for other methods of proof: algo.inria.fr/pfac/PFAC/Program_files/nicaud.pdf $\endgroup$ Nov 9, 2012 at 6:48
  • $\begingroup$ Neat. I did not know this before. $\endgroup$
    – Raphael
    Nov 9, 2012 at 7:40
  • $\begingroup$ 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. $\endgroup$ Nov 9, 2012 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).


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.