Let EVEN-CFL $=\left\{w | M_{w} \text { is a } \mathrm{TM}, \text { such that } L\left(M_{w} \right) \\ \text{ has only words with even length and is context free.}\right .\}$

Question : Is EVEN-CFL decidable?

Am trying to learn this type of proofs

Now the Rice-Theorem states, that semantic properties that are non-trivial are undecidable.

For this, EVEN-CFL is not a syntactic property of a TM, it's a property of the language and it's non-trivial because there exists languages that are context free and others that are not, like recursive languages or they have the length or not.

Is this right so far? How do I proceed now is this it? The use of the RICE-THEOREM



1 Answer 1


The property of being EVEN-CFL of c.e. languages is not trivial, by Rice's theorem this is not decidable.

  • $\begingroup$ Well. But I have understood the Rice theorem right, yeah? Non-trivial = For some it's right and for other's not. And semantic = about languages and syntactic about the TM itself? $\endgroup$
    – Rapiz
    Mar 19, 2020 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.