9
$\begingroup$

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?

$\endgroup$

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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}$? $\endgroup$
    – Numerator
    May 22, 2012 at 7:19
  • 2
    $\begingroup$ 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. $\endgroup$ May 22, 2012 at 11:31
  • $\begingroup$ 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$.. $\endgroup$
    – Numerator
    May 22, 2012 at 13:40
  • 1
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    May 22, 2012 at 18:02
  • $\begingroup$ 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 $\endgroup$
    – Numerator
    May 23, 2012 at 8:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.