UGC NET CSE | December 2019 | Part 2 | Question: 48

Question

Consider the following languages:

$L_1 = \{ a^nb^nc^m \} \cup \{a^nb^mc^m\}, n, m \geq 0$

$L_2 =\{ww^R \mid w \in\{ a, b \}^*\}$ Where $R$ represents reversible operation.

Which one of the following is (are) inherently ambiguous languages(s)?

• A. Only $L_1$
• B. Only $L_2$
• C. both $L_1$ and $L_2$
• D. neither $L_1$ nor $L_2$

Comments

This can be done only by hit and trial method.

---

https://cs.stackexchange.com/questions/6568/inherent-ambiguity-of-the-language-l-2-anbmcm-m-n-geq-1-cup-a

---

Actually I know that there is a mistake in that.

Actually I was going to write the answer for this so for reference I added the sources.

Anyway you have written so its good.

Thanks.

Answer 1

Answer : 1

$L1$ is inherently ambiguous language because we cannot have any unambiguous grammar for this language.

Specifically, ( Hopcroft & Ullman (1979) gives a proof) that there is no way to unambiguously parse strings in the (non-context-free) common subset $\{ a^nb^nc^n \}.$

https://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/inherently-ambiguous-language

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

$L2$ is Not inherently ambiguous and one unambiguous grammar for this language is :

$S \rightarrow aSa|bSb|\in$

It is not hard to show that the above grammar is unambiguous. (Hint : At every symbol, while reading the string from the left, you only have one choice of production rule in the parse tree.)

Comments

But actually there isn't any such algorithm.

The only way is the hit and trial and you managed to do this because you are aware of the related things, right?

---

@deepak sir

isn’t this grammar for L1 unambiguous?

 S → aMbX | aNYc

M → aMbX | $\epsilon$

N → aNYc | $\epsilon$

X → c | $\epsilon$

Y → b | $\epsilon$

---

 

isn’t this grammar for L1 unambiguous?

 S → aMbX | aNYc

M → aMbX | ϵ

N → aNYc | ϵ

X → c | ϵ

Y → b | ϵ

String “abc” can be derived in two different ways. 

S → aMbX →  abc

S →  aNYc →  abc

The language L1 has been proven to be ambiguous and that No unambiguous grammar is possible for L1. The proof is way beyond GATE or even MTech level. 

---

oh yes, my bad. Thanks sir

Answer 2

Answer : 1

$L1$ is inherently ambiguous language because we cannot have any unambiguous grammar for this language.

Specifically, ( Hopcroft & Ullman (1979) gives a proof) that there is no way to unambiguously parse strings in the (non-context-free) common subset $\{ a^nb^nc^n \}.$

https://www.encyclopedia.com/computing/dictionaries-thesauruses-pictures-and-press-releases/inherently-ambiguous-language

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

$L2$ is Not inherently ambiguous and one unambiguous grammar for this language is :

$S \rightarrow aSa|bSb|\in$

It is not hard to show that the above grammar is unambiguous. (Hint : At every symbol, while reading the string from the left, you only have one choice of production rule in the parse tree.)

Answer 3

Ans is D.

A language is called inherently ambiguous languages if we are not able to find a unambiguous grammar for the language.

But in this case we have the unambiguous grammar for both L1 and L2 languages. so the correct ans is D

 

L1={anbncm}∪{anbmcm},n,m≥0

unambiguous grammar for L1=

S → X | Y

X → UV

U → aUb | ∊

V → cV |  ∊

Y → WX

W → aW |  ∊

X → bXc |  ∊

 

 

L2={wwR∣w∈{a,b}∗}

unambiguous grammar for L2 =

S → aSa | bSb | ∊