I am trying to find a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$, but I can't seem to find one.

Definitions: $$\begin{align*} CF_{TM} &= \left\{ \langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is context-free} \right\} \\ A_{TM} &= \left\{ \langle M,w \rangle \mid \text{$M$ is a TM and $w \in L(M)$} \right\} \end{align*}$$

AFAIK the mapping reduction of the regular (i.e., not the complimentary) language is as follows: $\langle M,w \rangle \in A_{TM}$ if and only if we can construct a language $L$ which is context-free in the sense that $L(F((\langle M,w \rangle)))$ is context-free.

  • $\begingroup$ You write about a $L(F((\langle M, w \rangle)))$. What is this supposed to mean? $\endgroup$ – dkaeae Apr 8 at 9:23
  • $\begingroup$ that if x exists in $A_{TM}$ then there should be a x in f(x) to make the reduction, when f(x) is CF. so i need to take language as a function of A_TM and make it an instance of $CF_{TM}$. i think i should've chosen the function to be for $a^2^n$ format, because if $A_{TM}$ accepts it then a* is regular and also a CFL, and if it doesn't accept then it is not a cfl. but my main problem is why the compliment. could you please help me with that? $\endgroup$ – hps13 Apr 8 at 9:40

Let $L$ be recursively enumerable but not context-free (and, therefore, not empty). We only need the existence of such an $L$; the actual choice is immaterial. In addition, recall the empty set $\varnothing$ is context-free. The idea is to map to a TM which accepts $L$ in case $M$ accepts $w$ (i.e., $\langle M,w \rangle \in A_{TM}$) and to $\varnothing$ otherwise.

Given an instance $\langle M,w \rangle$ of $A_{TM}$, map it to the description $\langle S \rangle$, where $S$ is the TM which does the following:

On input $w'$:

  1. Run $M$ on $w$. If $M$ rejects, reject.
  2. If $M$ accepts $w$, then accept if and only if $w' \in L$.

Note that, if $M$ does not halt on $w$, then $S$ does not halt either. Also, $w' \in L$ can be checked because $L$ is recursively enumerable (and $S$ need not halt in case that is false). We conclude that $L(S) = L$ if $\langle M, w \rangle \in A_{TM}$ and $L(S) = \varnothing$ (which is context-free) otherwise.

An observation. The trick behind 98% of these problems lies in understanding what you need to do (i.e., what I wrote in the first paragraph). The actual description for the instance you are reducing to (in this case, $\langle S \rangle$) might look tricky or esoteric at first sight, but it actually simply follows as a consequence once you have the right ideas in mind.


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.