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\}$
Inherent ambiguity of the language $L_2 = \{a^nb^mc^m \;|\; m,n \geq 1\}\cup \{a^nb^nc^m \;|\; m,n \geq 1\}$
formal languages;formal grammars;context free;ambiguity
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.