1 of 1

Both of them are unrecognizable by the following lemma:

Lemma. Let $$\mathcal{L}$$ be a set of languages. If there exists two language $$L_1$$ and $$L_2$$ such that:

• $$L_1\subseteq L_2$$,
• $$L_1\in \mathcal{L},L_2\notin\mathcal{L}$$, and
• $$L_1$$ is decidable by a decider $$M_1$$, $$L_2$$ is recognizable by a TM $$M_2$$,

then the language $$L=\{\langle M\rangle\mid L(M)\in\mathcal{L}\}$$ is unrecognizable.

Proof. Suppose $$L$$ is recognizable by a TM $$M_L$$. We will construct a TM that recognizing $$\overline{H_{\mathrm{TM}}}=\{\langle M,w\rangle\mid M\text{ does not halt on }w\}$$, which is known as unrecognizable, hence a contradiction. The TM works as follows.

On input <M, w>:
1. Construct a TM N (using M and w) working as follows:
On input x:
1. Run M_1 on x, and accept if M_1 accepts
2. Run M on w
3. Run M_2 on x, and accept/reject if M_2 accepts/rejects
2. Run M_L on <N>, and accept/reject if M_L accepts/rejects


Note this TM accepts $$\langle M,w\rangle$$ if and only if $$M_L$$ accepts $$\langle N\rangle$$, which means $$L(N)\in\mathcal{L}$$. Also note

$$L(N)=\begin{cases} L_2 & \text{if M halts on w},\\ L_1 & \text{otherwise}, \end{cases}$$

so the TM accepts $$\langle M,w\rangle$$ if and only if $$M$$ does not halt on $$w$$, which indeed recognizes $$\overline{H_{\mathrm{TM}}}$$.

Now if $$\mathcal{L}$$ is the set of context free languages, we can choose $$L_1=\emptyset$$ and $$L_2=\{a^nb^nc^n\mid n\ge 0\}$$, and using the lemma to show $$CF_{TM}=\{\langle M\rangle\mid L(M)\in\mathcal{L}\}$$ is unrecognizable. If $$\mathcal{L}$$ is the set of non-context free languages, we can choose $$L_1=\{a^nb^nc^n\mid n\ge 0\}$$ and $$L_2=\Sigma^*$$, and using the lemma to show $$\overline{CF_{TM}}$$ is unrecognizable.