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.