Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



Consider the following languages:

$L_1={a^n b^n c^m}\cup{a^n b^m c^m},\ n,m\ge 0$

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

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






Solution

$L_1={a^n b^n c^m}\cup{a^n b^m c^m}$ is a standard example of an inherently ambiguous language.

Reason: strings of the form $a^n b^n c^n$ can be generated from both parts:

First part: $a^n b^n c^m$ when $m=n$

Second part: $a^n b^m c^m$ when $m=n$

So, ambiguity is unavoidable for $L_1$.

Now,

$L_2={ww^R\mid w\in{a,b}^*}$ is the language of even length palindromes.

This language is context-free and not inherently ambiguous.



Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...