What makes a context free grammar ambiguous?
What makes a context free grammar ambiguous?
-
0Have you looked at the examples [here](http://en.wikipedia.org/wiki/Ambiguous_grammar)? – 2011-01-16
-
0Are you asking for a definition or some kind of intuitive explanation? – 2011-01-16
4 Answers
A grammar is ambiguous if there's a word which has two different derivation trees. You'll have to look up derivation tree in your textbook since drawing them is awkward, but the idea that it doesn't matter in which order you're doing the derivations as long as it's basically the same derivation.
For example, consider the grammar \begin{align} S &\rightarrow AS|a \\ A &\rightarrow a \end{align}
Let's derive $aa$ twice: $$ S \rightarrow AS \rightarrow Aa \rightarrow aa $$ $$ S \rightarrow AS \rightarrow aS \rightarrow aa $$ These derivations share the same derivation tree:
However, consider now the grammar \begin{align} S\rightarrow SS|a \end{align}
generating the same language.
There are now two "really" different derivations for $aaa$: $$S \rightarrow SS \rightarrow Sa \rightarrow SSa \rightarrow Saa \rightarrow aaa$$ $$S \rightarrow SS \rightarrow aS \rightarrow aSS \rightarrow aaS \rightarrow aaa$$
In the first derivation, the first two $a$'s are derived together, whereas in the second derivation, it is the second two $a$'s which are derived together. So it's $(aa)a$ vs. $a(aa)$.
In this case, the language $a^+$ has an unambiguous grammar (the first one I exhibited), but in other cases, all grammars are ambiguous; such languages are called inherently ambiguous. See my other answer for more on that.
-
0Note that "basically the same derivation" is also denoted by using the terms *(left|right) derivation*. – 2011-03-04
-
1There might be more than two derivations in general. – 2011-03-04
-
0@YuvalFilmus:Could you explain the difference between the two examples.I can't see any difference and it might be because I'm weak in CFG's. – 2016-02-12
-
0@justin You have to look at the derivation tree. Find a source explaining them, and draw the trees. – 2016-02-12
-
0@YuvalFilmus:Sorry to bother but I see a difference in the parse tree in the first example.While we draw the parse tree for each we could see that at first level there is (S) for both then at 2nd level it's (A S) for both while we enter the 3rd level we could see (A a) for 1st derivation and (a S) for 2nd derivation even though the 4th level is (a a) for both.Isn't there a difference in level 3? – 2016-02-12
-
0@justin There is no fourth level in these trees. – 2016-02-12
-
0@YuvalFilmus:Could you tell why don't you include _Aa_ and _aS_ in the derivation tree in the first example.If that's too included in the first example we would get four levels where the extra level would be _Aa_ and _aS_. – 2016-02-25
-
0@justin Because that's not how derivation trees work. I suggest you consult your textbook regarding them. – 2016-02-25
-
0@YuvalFilmus:Yeah that's right.It's my fault.I should have read this [link](http://www.cs.umd.edu/~lam/cmsc330/summer2012/lectures/class09-cfgs.pptx) before asking you questions. – 2016-03-22
-
1This answer is incorrect; it should be more than one LEFTMOST derivation. Not just more than one derivation. – 2018-11-07
Intuitively, what makes a language inherently ambiguous is that it is composed of distinct parts which have some intersection; the intersection cannot be "singled out", and therefore the only way to approach is is through the distinct parts.
For example, the language of words of the form $a^xb^yc^z$, where $x=y$ or $y=z$, is context-free, since it's the union of $a^nb^nc^*$ and $a^*b^nc^n$. However, words of the form $a^nb^nc^n$ cannot be "singled out" since that language is not context-free, so we would expect the language to be inherently ambiguous.
The formal proof (using Ogden's lemma) goes like this. Consider the word $a^nb^nc^{n!}$, where $n$ is "big enough". By Ogden's lemma, the $a^nb^n$ can be pumped up, and so we can derive $a^{n!}b^{n!}c^{n!}$. Similarly, we can derive the same word from $a^{n!}b^nc^n$. The two derivations overlap (over the middle part) and so must be "inherently" different (i.e. have different derivation trees).
Another example, from the world of regular languages, is as follows. Consider the language over the alphabet $\{a,b\}$ of all non-empty words having either an even number of $a$'s or an even number of $b$'s (or both). Does it have a disjoint representation as a union $L_1^+ \cup \cdots L_m^+$ (here $+$ is the Kleene plus)? Intuitively, the problem is that a word with both $a$ and $b$ even is "ambiguous".
The formal proof goes by the usual pumping lemma. Pick an odd $n$ that is greater than the pumping length of all $L_i^+$'s in a given representation. The word $a^n b^{n!}$ is generated by a unique $L_i^+$. By the pumping lemma, $L_i^+$ also generates $a^{n!} b^{n!}$. Similarly, the word $a^{n!} b^n$ is generated by a unique $L_j$, which also generates $a^{n!} b^{n!}$. If $i=j$ then $L_i^+$ generates the concatenation, which has both $a$ and $b$ odd - so $i \neq j$ and we get inherent ambiguity.
-
1Are you certain this is a necessary criterion? – 2011-03-04
-
1No, but all the examples I know are of this form. It is conceivable that there are other, wildly different specimens. – 2011-03-04
One of the criteria is structure of recursion. If your grammar is both left and right recursive, which means it can be expanded to both left side and right side, then the grammar is absolutely ambiguous.
However, this does not mean that the grammar with only left recursion or right recursion cannot be ambiguous. There may be another criterion which makes that grammar ambiguous.
A grammar said to be ambiguous if it has multiple derivations for a word. if there are 1000 word for which grammar has unique way , but even for one word it has more than one path it will said to be ambiguous. Lets look in the following examples :
Example 1 :
S -> XaaX/ aX
X -> Xa/Xb/ ^
let us drive one word "aabaa" from two ways:
S => XbaaX => Xa baaX => Xa abaa ^ => ^aabaa => aabaa
S => aX => a Xa => a Xa a => a Xb aa => a Xa baa => a ^ abaa => aabaa
Example 2:
S → AB | C A → aAb | ab B → cBd | cd C → aCd | aDd D → bDc | bc
now we will drive aabbccdd from two ways
S => AB => aAb cBd => aabbccdd
S=> C => aCd => aaDdd => aa bDc dd => aab bc cdd => aabbccdd