# Rice theorem G is a CFG. Is L(G)= Σ ∗ L(G)=Σ∗ .What is it - Decidable / Undeciable .How?

162 views
0

This problem is reducible to Post correspondence problem which is undecidable.

0
I am Unable to read this problem,may you brief little bit more

## Related questions

1
220 views
L = {<M1, M2>M1 and M2 are two TMs, and ε ∈ L(M1) \ L(M2) }. is it RECURSIVE OR RECURSIVE ENUMERABLE OR NOT EVEN RECURSIVE ENUM.
2
173 views
1.{<M>| M is a TM accepts any string starting with 1} 2.{<M>| M is TM accept exactly 20 strings} Please guide I don’t know how to apply rice theorem. for 1. Is Tyes = { string starting with 1} Tno = { all strings – strings starting with 1} what is Tyes and Tno here? I only conclude by intution that when we provide strings as input some got into loop and some got accepts .
3
124 views
L1 = { <M> | M is a TM and | L (M) <=1 } L2= { <M> | M is a TM and | L (M) >=1 } NOW QUESTION IS WHICH ARE RECURSIVE ENUMERABLE AND WHICH ARE NOT ???? I JUST READ BASICS OF rice theorem DONT PRACTICE MUCH QUESTIONS ON THIS I SOLVED ABOVE QUESTION BY THIS... ... string length >= 0...... and REL_yes as string length >= 1 . REL_YES is a proper subset of REL _NO . so we can say that it is also non re