0
$\begingroup$

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

Thanks

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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 that you have read and understand our privacy policy and code of conduct.

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