The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
75 views

how to solve  this ques [email protected] Gupta 2

asked in Theory of Computation by (437 points) | 75 views
0
0
Both are NOT RE. So, Answer D.
0
+1
Thanks Prashant Sir and Deepak Bhaiyya..I forgot to think of the non recognizability

1 Answer

0 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)

answered by Boss (18.2k points)
edited by


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,437 questions
46,622 answers
139,355 comments
57,007 users