So, let's say we have two languages $L$ (which is any context-free language) and $M$ which is the basic CFL $\{0^n1^n: n\geq 0\}$.

Can $L \le_p M$ ? Why or why not? How do polynomial time reductions even work with CFLs in general?


1 Answer 1


Since context-free languages are in P and $M$ is non-trivial, there is an easy polynomial time reduction from every context-free language $L$ to $M$. The reduction decides whether the input is in $L$ or not, and according to that outputs either $\epsilon$ or $0$, say.

  • $\begingroup$ trivial languages can be a context-free language. Therefore the reduction will fail if L is the empty language $\endgroup$
    – ParoX
    Dec 6, 2014 at 21:31
  • $\begingroup$ No it won't. In that case the reduction would just be a constant function. $\endgroup$ Dec 6, 2014 at 22:09
  • $\begingroup$ As I understand it, The reduction stated here wouldn't work though, because it relies on weather an input is in L or not, in the case of the empty language it would always return that the input was not in the language and be useless. I guess my point was that there is a specific instance where this particular reduction doesn't work $\endgroup$
    – ParoX
    Dec 6, 2014 at 22:19
  • $\begingroup$ I think you're wrong. It's only important that $M$ be nontrivial. $\endgroup$ Dec 6, 2014 at 22:20

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.