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 properties of recursively enumerable sets:

(A) Finiteness
(B) Context Freedom
(C) Emptiness
Which of the following is true?





Solution

For recursively enumerable sets, these properties are related to languages accepted by Turing machines.

Now check each property one by one.

(A) Finiteness:

To decide whether a recursively enumerable language is finite or infinite, we need to know all strings accepted by the Turing machine.

But a Turing machine may not halt on some inputs.

So, finiteness of recursively enumerable sets is not decidable.

(B) Context Freedom:

To decide whether a recursively enumerable language is context-free or not is also not decidable.

This is a non-trivial property of the language accepted by a Turing machine.

By Rice's theorem, every non-trivial property of recursively enumerable languages is undecidable.

So, context freedom is not decidable.

(C) Emptiness:

Emptiness means checking whether the language accepted by a Turing machine is empty or not.

That is, we need to decide whether the Turing machine accepts at least one string.

This is also undecidable for recursively enumerable languages.

Therefore, all three properties are not decidable.


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