399 views
0 votes
0 votes

how to solve  this ques sir@Rishab Gupta 2

1 Answer

Best answer
1 votes
1 votes

Answer : D


Quick Revision :

Rice's Theorem Part 1 (For some undecidable languages) :

We know by Rice's theorem that "Any non-trivial property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is undecidable". 

For a property of recursively enumerable set to be non-trivial, there should exist at least two recursively enumerable languages, (hence two Turing machines), the property holding for one ($T_{yes}$ being its TM) and not holding for the other ($T_{no}$ being its TM).

Thus, as per Rice’s theorem the language describing any nontrivial property of Turing machine is not recursive. It can either be recursively enumerable or not recursively enumerable. 

Rice's Theorem Part 2 (For some unrecognizable languages) :

Any non-monotonic property of the LANGUAGE recognizable by a Turing machine (recursively enumerable language) is unrecognizable.  

For a property of recursively enumerable set to be non-monotonic, there should exist at least two recursively enumerable languages (hence two Turing machines), the property holding for one ($T_{yes}$ being its TM) and not holding for the other ($T_{no}$ being its TM) and the property holding set (language of $T_{yes}$) must be a proper subset of the set not having the property (language of $T_{no}$).

https://gatecse.in/rices-theorem/


1. $REG = \left \{ M \,\,| \,\,L(M) \,\,is\,\, Regular \right \}$

It is Non-trivial property of Turing Machines because Not every RE language is Regular. You could have two TM $M_1$ and $M_2$ such that $L(M_1)$ is Regular whereas $L(M_2)$ is Non-regular. Hence, The given language $REG$, by Rice's theorem part 1, is Undecidable(i.e. Not REC)

Moreover, "$L(M)$ is Regular"   is a Non-monotonic property. Because you could give Two TM $M_{yes}$ and $M_{no}$ such that $L(M_{yes})$ is Regular, say, $L(M_{yes}) = \phi$ and $L(M_{no})$ is Non-regular, say, $L(M_{no}) = ww$ and We can see that $L_{yes} \subset L_{no}$. Hence, The given language $REG$, by Rice's theorem part 2, is Unrecognizable (NOT RE)


2. $Co-Reg$ $= \left \{ M \,\,| \,\,L(M) \,\,is\,\, Non-Regular \right \}$

It is Non-trivial property of Turing Machines because Not every RE language is Non-Regular. You could have two TM $M_1$ and $M_2$ such that $L(M_1)$ is Regular whereas $L(M_2)$ is Non-regular. Hence, The given language $Co-REG$, by Rice's theorem part 1, is Undecidable(i.e. Not REC)

Moreover, "$L(M)$ is Non-Regular"   is a Non-monotonic property. Because you could give Two TM $M_{yes}$ and $M_{no}$ such that $L(M_{yes})$ is Non-Regular, say, $L(M_{yes}) = ww$ and $L(M_{no})$ is Regular, say, $L(M_{no}) = \Sigma^*$ and We can see that $L_{yes} \subset L_{no}$. Hence, The given language $Co-REG$, by Rice's theorem part 2, is Unrecognizable (NOT RE)

selected by

Related questions

0 votes
0 votes
0 answers
2
baofbuiafbi asked Nov 14, 2023
152 views
Prove the language L={(G,H)|G is a CFG, H is a DFA, and L(G)∩L(H)=∅} is undecidable.