Problem Detail: 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}$
Asked By : Shashwat
Answered By : Yuval Filmus
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 $qleq 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/6568
