Aspire's Library

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

Previous Year Question (PYQs)



Let $G_1$ and $G_2$ be arbitrary context free languages and $R$ an arbitrary regular language. Consider the following problems:

$(A)$ Is $L(G_1)=L(G_2)$?

$(B)$ Is $L(G_2)\subseteq L(G_1)$?

$(C)$ Is $L(G_1)=R$?

Which of the problems are undecidable?





Solution

For context free languages, equivalence problem is undecidable.

So,

$L(G_1)=L(G_2)$ is undecidable.

Also, inclusion problem for context free languages is undecidable.

So,

$L(G_2)\subseteq L(G_1)$ is undecidable.

Now,

$L(G_1)=R$

is also undecidable because if $R=\Sigma^*$, then this becomes CFL universality problem:

$L(G_1)=\Sigma^*$

which is undecidable.

Therefore, all three problems are undecidable.


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