patternModerate
Inherent ambiguity of the language $L_2 = \{a^nb^mc^m \;|\; m,n \geq 1\}\cup \{a^nb^nc^m \;|\; m,n \geq 1\}$
Viewed 0 times
inherentthegeqambiguitylanguagecupl_2
Problem
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
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
If you need,
$L_2$ can be written as $\{a^nb^pc^m\;|\; n=p \;\; or \;\; m=p\}$
$$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\}$
Solution
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.
Context
StackExchange Computer Science Q#6568, answer score: 13
Revisions (0)
No revisions yet.