-1
$\begingroup$

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.

$\endgroup$
6
  • $\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$ Jun 8, 2016 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, 2016 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, 2016 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, 2016 at 8:25
  • $\begingroup$ One thing to think about are complements of CFLs. $\endgroup$
    – Raphael
    Jun 8, 2016 at 8:25

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

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.