Let M range over Turing machine descriptions. Consider the set REG and let the complement of REG be Co-REG.

Question

Let M range over Turing machine descriptions. Consider the set REG= {M | L(M) is a regular set} and let the complement of REG be Co-REG. Which of the following is true?

(A) REG is r.e. but Co-REG is not
(B) REG is not r.e. but Co-REG is
(C) Both are r.e.
(D) None of them are r.e.

Comments

http://math.stackexchange.com/questions/1551527/let-m-range-over-turing-machine-descriptions-consider-the-set-reg-mlm-is-a

Refer this one

---

both are not re ?

---

yes, both are not RE.

---

explain??????

Answer 1

REG contains the set of all strings which are encodings of TM whose language is regular. So, REG is deciding a property of TM- we are lucky and can make use of Rice's theorem. 

Here we want to prove whether RE or not. (Rice's theorem part 1 won't help)

So, lets see if the property is non-monotonic so that we can apply Rice's theorem part 2. 

For non-monotonicity, language of TM satisfying the property must be a subset of language of TM not satisfying the property. So, if we take L(TM_yes) = ∅ and T(TM_no) = any non regular language, this proves the property is non-monotonic. So, as per Rice's theorem part 2, REG is not RE. 

Using the same technique we can prove Co-Reg is also not RE. Just take L(TM_yes) = any non regular language and L(TM_no) = Σ*. 

http://gatecse.in/wiki/Rice%27s_Theorem_with_Examples

Comments

Sir, can you explain me why L(TM yes)= phi and L(TM no)=any non regular language in your answer? I am facing difficulties in understanding how L(TM yes) and L(TM no) are found in any problem related to rice's theorem.

Answer 2

1).  REG = {<M> | L(M) is a regular set } 

Rice second theorem can help here => 

Take T_yes = {0,1,10,01} and T_No = (0,1)*

Now, as T_yes is a proper subset of T_No , hence, making this language even not RE.

2). Complement of REG 

Apply rice second theorem again =>

Take T_yes = Any non regular language like CFL or CSL and T_No = (0,1)*

Now, again as T_yes is a proper subset of T_No , hence, making this language even not RE.

Comments

Thanks.btw I mean pdf\site related to extended rice

Answer 3

L(M) is a regular set is a non-monotonic property of r.e. languages and deciding any such property is not even semi-decidable making REG non r.e.

For Co-Reg, L(M) is a non regular set, which is also a non-monotonic property of r.e. languages and hence Co-Reg is also non r.e.

So, D option.

http://www.gatecse.in/rices-theorem/ 

PS: To show monotonicity of a property, we need a r.e. language which has the property and another r.e. language which does not have the property and the first one a proper subset of second. For REG these languages respectively can be the empty language and any non-regular language (just one possibility) while for C-REG these respectively can be any non-regular language and $\Sigma^*$.

Answer 4

$\text{REGULAR}_{\text{TM}} = \left \{ <M>|\text{L(M) is regular} \right \}$

$\text{REGULAR}_{\text{TM}}$ is NOT RE  

Complement of $\text{REGULAR}_{\text{TM}}$ is also NOT RE.

Proofs of both of them are very rigorous :

1. Using reduction from complement of halting problem.

2. Using reduction from diagonalization language.

References : 1.    using complement of halting problem.

2. using diagonalization language

Comments

Here is a detailed and rigorous proof =>

http://cs.stackexchange.com/questions/11181/how-to-show-that-a-function-is-not-computable

---

real stuff ! thank you !

---

you're welcome :)