1
$\begingroup$

How would I reduce $A_{TM}$ to $CF_{TM}$ when: $A_{TM}=\{<M,w>|M$ is a Turing Machine description and $w\in L(M)\} $

$CF_{TM} =\{<M> | M$ is a Turing Machine description $L(M)$ is a context-free language.$\}$

My problem is this: $A_{TM}$ deals with all $TM$s how would knowing if some $TM$'s language is $CF$ help us know if $w \in L(M)$ ?

$\endgroup$
  • $\begingroup$ Take a look at this post, and try to modify the proof to CFL. $\endgroup$ – Shaull Mar 20 '18 at 16:20
2
$\begingroup$

If I read you correctly, you have the reduction wrong. Essentially, you need to use a transformation $f$ from an instance of $A_{TM}$ to an instance of $CF_{TM}$ such that $$ \langle{M, w}\rangle\in A_{TM} \Longleftrightarrow L(f(\langle{M, w}\rangle)) \text{ is a CFL} $$ To this end, let's define $f(\langle{M, w}\rangle)$ to be the description of a TM $N$ where

N(x) =
   if x = a^(2^n) for some n
      return accept
   else if M(w) = accept and x = a^k for some k
      return accept

Now if $\langle{M, w}\rangle\in A_{TM}$, it's clear that $L(N)=a^*$, the language of all strings of as which, being regular, is certainly a CFL. On the other hand, if $\langle{M, w}\rangle\notin A_{TM}$ then we skip the else part of the code of $N$ and so $$ L(N) = \{a^{2^n}\mid n\ge 0\} $$ which is well-known to be not a CFL.

This, by the way is a very handy idiom: have both parts accept a non-"whatever" language and the last part activate to add enough strings to get what you need to make a "whatever" language.

$\endgroup$
  • $\begingroup$ else if M(w) = accept and |x| = a^k for some k...you mean else if M(w) = accept and x = a^k for some k ? $\endgroup$ – Anwar Saiah Mar 21 '18 at 5:45
  • $\begingroup$ It is also not so clear for me, why L(N) is CFL or REGULAR when you say "if M(w) = accept and x = a^k for some k"..you have to define what x is for that matter cause there's no such input. Our input is just <M,w>. $\endgroup$ – Anwar Saiah Mar 21 '18 at 5:51
  • $\begingroup$ Other than that your solution is very convincing, but needs to be more clarified, Thanks. $\endgroup$ – Anwar Saiah Mar 21 '18 at 5:53
  • $\begingroup$ @AnwarSaiah. First, thanks for the catch about $|x|$, it's now fixed. For your second comment, if $M$ accepts $w$, then $N$ will accept any string of $a$s and only those, so $L(N)$ in that case is $a*$ $\endgroup$ – Rick Decker Mar 21 '18 at 16:18

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.