Let M range over turing machine descriptions .Consider the set REG={M|L(M) is a regular set} which of the statements are true? The complement of REG is Co-REG 


*

*REG is recursively enumerable but Co-REG is not 

*REG is not recursively enumerable but Co-REG is 

*Both are recursively enumerable
4.None of them are recursively enumerable


According to me if the language accepted by turing machine is a regular set then clearly the complement of regular set  should be a regular set as well so then why are we using the terminology of recursively enumerable sets here ?
 A: Let us first prove that REG is not RE. I will use the book Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman.
$\newcommand{\S}{\mathcal S}$
Let $\S \subset RE$ a set of recursive languages, and $L_{\S} = \{ <M>, L(M) \in \S \}$ ($<M>$ denotes here the an encoding of the TM M, so that we clearly define $L_{\S}$ as a language.
We are interested to know whether $L_{REG} \in RE$.
Theorem 1
If $L_{\S} \in RE$, then $(\forall L \in L_{\S}), (\forall L' \in RE$ such that $L \subset L')$, we have $L' \in \S$.
Proof that $L_{REG} \not \in RE$ using theorem 1
Be $l_1 \in REG$, there are clearly languages containing $l_1$ that are not regular, and as such $L_{REG} \not \in RE$.
Proof of the theorem 1
Be $L_1 \in \S, L_2 \in RE$ such that $L_1 \subset L_2$ and $L2 \not \in \S$. Be $M_1, M_2$ turing machines recognising $L_1$ and $L_2$ respectively.
Let us suppose $L_{\S} \in RE$, and be $M_{\S}$ a TM that accepts $L_{\S}$

Reminder: 
Be $L_u = \{ <M,w>, \text{ M accepts w } \}$ the universal language. Neither $L_u$ nor $\bar{L_u} = \{ <M,w>, \text{ M does not accept w } \}$ are decidable.
To get a contradiction in our hypothesis, we will show $\bar{L_u}$ is decidable.

Be $A$ be the TM that takes $<M,w>$ as input, and the following machine $M'$ as an output : 
We have the following : 


*

*If $w \in L(M)$, then $L(M') = L_2 \not \in L_{\S}$

*If $w \not \in L(M)$, then $L(M') = L_1 \in L_{\S}$


So that $L(M') \in L_{\S}$ iff $w \not \in L(M)$.
We know build a second TM : 
Putting everything together, we get that this TM accepts $<M,w>$ iff $L(M') \in \S$ iff  $M$ does not accept $w$. This TM decides $\bar{L_u}$, which is impossible.


We also have $L_{Co-REG} \not \in RE$ from another theorem which I will not prove here (it is in the same book):  
Theorem 2
If $\S$ contains an infinite language $L$ such that there is no finite subset of $L$ in $\S$, then $L_{\S} \not \in RE$.
Proof that $L_{Co-REG} \not \in RE$
There clearly are infinite languages in Co-REG. Let us pick one : $L$. Since any finite language is in REG, there is no finite subset of $L$ in Co-REG, and thus Co-REG $\not \in RE$
