Inherently ambiguous grammar

Question

Q- Which one of following languages is inherently ambiguous?

(A) The set of all strings of the form $\left\{a^nb^n,n>0 \right\}$

(B) $\left\{a^nb^nc^md^m,n,m>0 \right\}$

(C) $\left\{a^nb^nc^md^m,n,m>0 \right\}\;\cup \;\left\{a^nb^mc^md^n,n,m>0 \right\}$

(D) Both (B) and (C)

Plz explain..

..........Is there any criteria on the basis of which we could identify inherently ambiguous grammar

Comments

Useful link: https://en.wikipedia.org/wiki/Ambiguous_grammar#Inherently_ambiguous_languages

Answer 1

Answer is C

Yes, there is some criteria to check inherent ambiguity

First of all , Inherent ambiguity term is used for language, not for grammar.

A language for which every grammar (you can design ) is ambiguous. 

There may be many grammar for one language 

say $L$ is $a^n \;,\;n> 0$ mean $a^+$ , $L =\left\{a,aa,aaa,aaaa,..\right\}$

There is  a CFG $S \rightarrow aS|Sa|a$ , which is ambiguous as we can derive one word say ,$aa$, using different ways and having different tree also. This CFG is ambiguous but language is not inherent ambiguous.

 because we have a CFG $S \rightarrow aS|a$ for same language that is unambiguous.

So you can say, for a language for which no unambiguous grammar is possible is inherent ambiguous language 

As in option C , language is two different language for which CFG cannot be designed without using 

$S\rightarrow S_1 | S_2$

where $S_1\rightarrow XY$

$X\rightarrow aXb | ab$

$Y \rightarrow cYd | cd$

and $S_2 \rightarrow aSd |aZd$

$Z\rightarrow bZc| bc$

This is only and only way to design CFG for Language. 

and This language is ambiguous also 

you can derive word $abcd$  using $S\rightarrow S_1$  and also Using $S\rightarrow S_2$ 

So Language is Inherent Ambiguous .

[other words you can check $aabbccdd$ or $aaabbbcccddd$ ..i,e common in both parts of language]

Comments

But only way is to follow trial and error?

---

Yes, Either we already know/practiced  some problems of inherent ambiguity.

In some case it is clear.  As in above problem

---

Since the problem is undecidable.

---

@Praveen Sir, @Arjun Sir, and checking whether the language or grammar is ambigous for CFL, DCFL, RE, REL is Undecidable because we have to find an unambiguous grammar for the language which are infinite for a language right??

---

for Every DCFL we can find an unambiguous grammar, corresponding to DPDA

---

Isn't option C a DCFL?

---

Oh no never mind.

---

@Praveen Sir, so can we say if we cannot have a DPDA for a CFL, it is inherently ambiguous ?

---

No, we can't say

---

Since, it is undecidable problem, then what we should do if there's an option of NONE OF THE ABOVE, and suppose we are trying harder and harder to produce some ambiguous grammar but not getting success, how much we should try before going for NONE option ?

---

Sir we can't say it because  some of the CFL gets the unambiguous grammar, isn't it.

---

Option C consists of two different languages, each of which has an unambiguous grammar.

So, now thing sure here is the start symbol of the language in option C will be like,        S → X1/X2 , where X1 will be the start symbol for the first part of Language and X2 for the second part.

This will help us give a unique parse tree for a string that belongs to either first language or second language but not both.

However, for the strings which lie in the intersection of these two languages {a^mb^mc^md^m}, we can have at least two parse trees. {S → X1, ….} and {s → X2 ….}

which makes the language inherently ambiguous.

Kindly let me know my mistake, if any

Answer 2

till DCFL a language must be unambiguous. i.e there must be exist a unambiguous grammar for dcfl language.

so at first we check a grammar is dcfl or not. if it is dcfl then we can easylly say it is unambiguous language.in this question option a and b is dfcl so it is unambiguous language. 

but for option c it is cfl . but not dcfl so we need to check there exist a grammar which is unambiguous.

Comments

Actually we can follow one strategy, a DCFL Language can be parsed by LR parser and all the language which can be parsed by a LR parser are unambiguous.