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?

$\endgroup$
4
  • $\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 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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