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$
1
  • $\begingroup$ Take a look at this post, and try to modify the proof to CFL. $\endgroup$
    – Shaull
    Commented Mar 20, 2018 at 16:20

1 Answer 1

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$
4
  • $\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$ Commented Mar 21, 2018 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$ Commented Mar 21, 2018 at 5:51
  • $\begingroup$ Other than that your solution is very convincing, but needs to be more clarified, Thanks. $\endgroup$ Commented Mar 21, 2018 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$ Commented Mar 21, 2018 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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