# Languages reducible to and from context-free

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.

• 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. Jun 8, 2016 at 7:45
• 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? Jun 8, 2016 at 7:53
• 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. Jun 8, 2016 at 8:23
• "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. Jun 8, 2016 at 8:25
• One thing to think about are complements of CFLs. Jun 8, 2016 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.