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

Problem Detail: 

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?

Asked By : Numerator

Answered By : Carl Mummert

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1979