# Proof that $\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$ is not (co-)recursively enumerable

I would like to use your help with the following problem:

$L=\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$. Show that $L \notin RE \cup CoRE$.

I know that to prove $L\notin RE$, it is enough to find a language $L'$ such that $L'\notin RE$ and show that there is a reduction from $L'$ to $L$ $(L'\leq _M L)$.

I started to think of languages which I already know that they are not in $RE$, and I know that $Halt^* =\{⟨M⟩ ∣ M\mbox{ halts for every input} \} \notin RE$. I thought of this reduction from $Halt^*$ to $L$: $f(⟨M⟩)=(M')$. for every $⟨M⟩$: if $M$ halts for every input $L(M')=0^n1^n$ otherwise it would be $o^n1^n0^n$, but this is not correct, Isn't it? How can I check that $M$ halts for every input to begin with? and- is this the way to do that?

I think the question is how to show that $L$ is not r.e. One way to do that is to reduce the complement of the halting problem to $L$, because the complement of the halting problem is not r.e.
Here's a hint about one way to do that reduction: given $M$ and $x$, we want to make a language that is context free if and only if $M(x)$ does not halt. So start simulating $M$ on input $x$. As long as $M(x)$ does not halt, we make a language that looks like $\{ 0^n : n \in \mathbb{N}\}$. But if $M(x)$ does halt, we change the language we're generating after that point to be some r.e. but not context free language.
• Thank you for the answer. Is it enough to immediate conclude that $\bar{L} \notin RE$ as well? or should I show in a similar way reduction from the complement of the halting problem to $\bar{L}$? – Numerator May 22 '12 at 7:19
• The easiest way to show that $L$ is not co-r.e. is to reduce (separately) the halting problem to $L$. That can be done in a way vaguely similar to the one I suggested for reducing the complement of the halting problem, except that you want to build a "bad" language until some machine halts, and then switch to a "good" language. – Carl Mummert May 22 '12 at 11:31
• Can you please explain how does reduction from the halting problem to L help us? we will then know that $L \notin R$, and we already know that $L \notin RE$.. – Numerator May 22 '12 at 13:40
• @Numerator, if we give a many-one reduction from a non-r.e. language $A$ to another language $B$, then not only $B$ is undecidable, it is also non-r.e. – Kaveh May 22 '12 at 18:02
• I know that. I am talking about showing that $L$ is not in core and I cant understand how does the suggested reduction help us, since reduction from the halting problem to $L$ does not gives us that L-NOT is not in Re – Numerator May 23 '12 at 8:55