7
$\begingroup$

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

$\endgroup$
  • 6
    $\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 '12 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 '12 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 '12 at 6:17
  • 3
    $\begingroup$ See here for a technique that might be useful here. $\endgroup$ – Raphael Nov 9 '12 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 '18 at 16:01
12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ See the following presentation for other methods of proof: algo.inria.fr/pfac/PFAC/Program_files/nicaud.pdf $\endgroup$ – Yuval Filmus Nov 9 '12 at 6:48
  • $\begingroup$ Neat. I did not know this before. $\endgroup$ – Raphael Nov 9 '12 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$ – Hendrik Jan Nov 9 '12 at 23:44
5
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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