Redirected
recategorized by
1,396 views
0 votes
0 votes

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)?

  1. Only $L_1$
  2. Only $L_2$
  3. both $L_1$ and $L_2$
  4. neither $L_1$ nor $L_2$
recategorized by

3 Answers

5 votes
5 votes

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.)

2 votes
2 votes

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.)

0 votes
0 votes
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 | ∊

Related questions

1 votes
1 votes
2 answers
1
4 votes
4 votes
6 answers
3
soujanyareddy13 asked May 12, 2021
1,860 views
The Boolean expression $AB+A \overline{B}+\overline{A}C+AC$ is unaffected by the value of the Boolean variable _________.$A$$B$$C$$A, B$ and $C$