2
$\begingroup$

I have searched the site well through, and also using Google and notes and couldn't find an answer to a question I am wondering about.

Given:

$$CF_{TM} =\{ \langle M \rangle \mid \text{$M$ is a TM description and $L(M)$ is a context-free language} \}$$

Are $CF_{TM}$,$\space $ $\overline{CF_{TM}}$ Turing-recognizable?

In order for a machine to be turing recognizable, there should exist a Turing machine that will halt and accept only string on that language, and for strings no in that language, it should reject or not halt at all.

So i am truly wondering about the relationship between context free languages and being Turing-recognizable, are $CF_{TM}$, $\space $ $\overline{CF_{TM}}$ Turing-recognizable?

$\endgroup$
  • 1
    $\begingroup$ You have defined $CF_{TM}$, but what is $CF_{TM} \overline{CF_{TM}}$? Is it the concatenation of $CF_{TM}$ and $\overline{CF_{TM}}$? $\endgroup$ – dkaeae Apr 1 at 8:51
  • $\begingroup$ it is the lack of space, i missed it when i reviewed my post before posting. fixing right now $\endgroup$ – CrimsonWater Apr 1 at 9:38
  • $\begingroup$ I still don't get it. Should the comma just be an "and"? $\endgroup$ – dkaeae Apr 1 at 9:41
  • $\begingroup$ is it more understandable now? i tried to fix it using proper spacing. i was asking if any of them are turing recognizable(not their concatenation, but each separately) $\endgroup$ – CrimsonWater Apr 1 at 9:43
  • $\begingroup$ Aha. Well, what have you tried? Hint: You could use Rice's theorem. $\endgroup$ – dkaeae Apr 1 at 9:49
3
$\begingroup$

This question describes a nice situation to introduce a partial version of the generalized Rice's theorem.

A partial version of the generalized Rice's Theorem

For $S$ be a subset of Turing-recognizable languages, let $L_S$ be the set of TMs that recognize a language in $S$, that is, $$L_S = \{ \langle M \rangle \mid L(M) \in S \}.$$ Suppose $L_1 \in S$, $L_1 \subset L_2$ and $L_2 \not\in S$. Then $L_S$ is not Turing-recognizable.

$CF_{\text{TM}}$ is not Turing-recognizable.

$CF_{\text{TM}}=L_{\text{CFL}}$, where $\text{CFL}$ is the set of all context-free languages. Let $L_1=\emptyset$ and $L_2=\{a^{n^2}\mid n\in \Bbb N\}$. Then $L_1\subset L_2$, $L_1\in \text{CFL}$, $L_2\not\in \text{CFL}$. So, $L_{\text{CFL}}$ is not Turing-recognizable.

$\overline{CF_{TM}}$ is not Turing-recognizable

$\overline{CF_{\text{TM}}}=\{ s : s\text{ is a string that does not encode a TM}\}\sqcup L_{\overline{\text{CFL}}}$, where $\overline{\text{CFL}}$ is the set of all non-context-free formal languages. Let $L_1=\{a^{n^2}\mid n\in \Bbb N\}$ and $L_2=\{a^n\mid n\in \Bbb N\}$. Then $L_1\subset L_2$, $L_1\in \overline{\text{CFL}}$, $L_2\not\in \overline{\text{CFL}}$. So, $L_{\overline{\text{CFL}}}$ is not Turing-recognizable.

Proof of the partial version of the generalized Rice's Theorem

Suppose $L_S$ is recognized by a TM $M_S$. We will construct a TM that recognizes $\overline{HALT_{\text{TM}}}=\{\langle M,w\rangle\mid M\text{ does not halt on }w\}$, which is known as not Turing-recognizable, hence a contradiction. The TM works as follows.


On input $\langle M, w\rangle$:

  1. Construct a TM $T_{M,w}$ that works as follows:

    On input $x$:

    • Run $M_1$ on $x$, and accept if $M_1$ accepts. Here $M_1$ is a TM that recognizes $L_1$.
    • At the same time, also run $M$ on $w$. If $M$ accepts, run $M_2$ on $x$, and accept if $M_2$ accepts. Here $M_2$ is a TM that recognizes $L_2$.
  2. Run $M_S$ on $T_{M,w}$, and accept if $M_S$ accepts.

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

$$L(T_{M,w})=\begin{cases} L_1 & \text{if $M$ does not halt on $w$},\\ L_2 & \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{HALT_{\mathrm{TM}}}$.

The above proof is a modified version of xskxzr's nice proof of his lemma in his answer.

Exercises

Exercise 1. Show that a context-free language (that is defined by a context-free grammar) is Turing-recognizable. Show that a non-context-free formal language (that is defined by an unrestricted grammar and that cannot be defined by a context-free grammar) is Turing-recognizable.

Exercise 2. (One minutes or two) Check that both the question and this answer remain valid if we replace "context-free" by "regular".

Exercise 3. Show that $\overline{\text{CFL}}$, the set of all non-context-free formal languages given by their grammars properly encoded by some fixed scheme, is not Turing-recognizable. Hence, $L_{\overline{\text{CFL}}}$ cannot be Turing-recognizable either.

EXercise 3. Read the full version of generalized Rice's Theorem. Can you prove it? (This might not be easy.)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

We can use Rice-Shapiro to prove that both are not recognizable.

Assume $CF_{TM}$ is recognizable. Take any $M$ where $L(M)=\emptyset$. By Rice-Shapiro, since $\langle M \rangle \in CF_{TM}$ we have that every $N$ such that $L(N)\supseteq L(M)=\emptyset$ (which is always true) satisfies $\langle N \rangle \in CF_{TM}$. We reach a contradiction choosing $N$ so that $L(N)$ is not context-free.

Assume $\overline{CF_{TM}}$ is recognizable. Take any $M$ where $L(M)=\{0^n1^n2^n \ | \ n\in\mathbb N\}$ which is not context-free. By Rice-Shapiro, since $\langle M \rangle \in \overline{CF_{TM}}$ there must exist some $N$ such that 1) $L(N)\subseteq L(M)$, 2) $L(N)$ is finite, and 3) $\langle N \rangle \in \overline{CF_{TM}}$. We reach a contradiction since $L(N)$, being finite, is context-free.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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