Let $L'$ be a context-free language. If $L \leq_M L' \leq_M L''$, where $\leq_M$ denotes mapping reducibility (aka many-one reducibility), what can we know about $L$ and $L''$?

I think they're both decidable languages but that's all I can say.

  • $\begingroup$ What exactly does $\leq_M$ stand for? Just many-one reducibility? Any restriction on the power of the machine that computes the reduction? You've already given an answer but you don't ask any specific questions about it so I'm not sure what you're really asking. $\endgroup$ – David Richerby Jun 8 '16 at 7:45
  • $\begingroup$ mapping reduction. The answer I gave is not very specific. Is there a way to conclude L or L" are also context-free? Or does it all depend on the reduction used? $\endgroup$ – Ricardo Jun 8 '16 at 7:53
  • $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jun 8 '16 at 8:23
  • $\begingroup$ "Or does it all depend on the reduction used?" -- of course! As a general rule, you can't get more resolution than the class of $M$ itself. $\endgroup$ – Raphael Jun 8 '16 at 8:25
  • $\begingroup$ One thing to think about are complements of CFLs. $\endgroup$ – Raphael Jun 8 '16 at 8:25

From $L \leq_M L' \leq_M L''$, we can only conclude that $L$ is decidable. It is because $L'$ is a context free language and hence decidable (If you need a proof, you can take a look at this Are all context-free and regular languages efficiently decidable?) . So, we can convert $L$ to $L'$ and then decide $L$.

But we can not do the same for $L''$. Because it might be possible to reduce $L'$ to $L''$ but after reduction we can not say that it can be decided in that reduced form.

| cite | improve this answer | |

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.