0
$\begingroup$

You know that Rice theorem is applicable to check decidability of RE language. Also we know that all regular, deterministic context free, context free, recursive languages are RE languages.

$Q_1:$ So my question is that could I apply Rice theorem to check decidability of for example emptiness, membership etc of CFL languages.

$Q_2:$ $$L_1= \{\langle M \rangle \mid \text{L(M) } = \phi\}$$ is undecidable for RE languages but $$L_2= \{\langle G \rangle \mid \text{L(G) } = \phi\}$$ is decidable for CFG. CFL is RE also. But why $L_1$ is undecidable but $L_2$ not, What's reason behind that?

Improve this question
$\endgroup$
5
  • $\begingroup$ You know that Rice theorem is applicable to check decidability of RE language. - what does it mean? Can you please give a link? Also, $L_2$ is not decidable too, see en.m.wikipedia.org/wiki/Context-free_grammar#Universality for $\phi=\Sigma^*$. $\endgroup$
    – Dmitry
    Oct 13, 2021 at 18:20
  • $\begingroup$ Please use \emptyset for $\emptyset$. Also, again, please give a link for applicable to decidability for RE language; it’s my first time hearing about it. $\endgroup$
    – Dmitry
    Oct 13, 2021 at 18:29
  • $\begingroup$ Exactly which sentence makes you think that Rice theorem is applicable to check decidability of RE language? I suspect that you miss the point that Rice's theorem talks about languages consisting of Turing machines, and it doesn't say anything about languages generated by these machines. (Your hope is wrong!!!!!!!!!) $\endgroup$
    – Dmitry
    Oct 13, 2021 at 18:48
  • $\begingroup$ It doesn't seem to go anywhere, so I'm out. Looking at your other questions, you seem to be a beginner in this area, so I suggest you reconsider your conviction that you fully understand the theorem. $\endgroup$
    – Dmitry
    Oct 13, 2021 at 18:56
  • 1
    $\begingroup$ Rice's theorem is about languages of Turing machines. It doesn't apply to languages of context-free grammars. $\endgroup$
    – Yuval Filmus
    Jul 10, 2022 at 21:18

1 Answer 1

Reset to default
0
$\begingroup$

When domain is Unrestricted grammars i.e. $G$ can be any $Type-0$ grammar and then if it is asked "whether $L(G)$ is CFL or not" ....is Undecidable (Because of Rice's theorem) otherwise decidable. That's why $Q_1$ is undecidable and $Q_2$ is decidable.

Improve this answer
$\endgroup$

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.