UGC NET Computer Science December 2019 | Question 98

Question 98

---

Consider the following languages :
L1={aⁿbⁿc^m} ∪ {aⁿb^mc^m}, n,m>=0
L2 ={ww^R | w ∈ {a, b}*} Where R represents reversible operation.
Which one of the following is (are) inherently ambiguous language(s)?

1. (1) only L1
2. (2) only L2
3. (3) both L1 and L2
4. (4) neither L1 nor L2

Answer : (1) only L1

Explanation

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ⁿbⁿcⁿdⁿ | n > 0}.
Reference : Inherently ambiguous languages

L2 is Not inherently ambiguous and one unambiguous grammar for this language is :
S→aSa|bSb|ε
A typical derivation in this grammar is S → aSa → aaSaa → aabSbaa → aabbaa.
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.)

So, option 1 is correct answer.

Previous	Next
UGC NET CS December 2019 - Question 97	UGC NET CS December 2019 - Question 99