Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
3  
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
3  
See here for a technique that might be useful here. –  Raphael Nov 9 '12 at 7:33
add comment

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
1  
See the following presentation for other methods of proof: algo.inria.fr/pfac/PFAC/Program_files/nicaud.pdf –  Yuval Filmus Nov 9 '12 at 6:48
    
Neat. I did not know this before. –  Raphael Nov 9 '12 at 7:40
    
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
add comment

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

share|improve this answer
    
Yes. I checked that. Thank you. –  Shashwat Nov 9 '12 at 6:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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