Problem Detail: 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: ngeq 0}$. Can $L le_p M$ ? Why or why not? How do polynomial time reductions even work with CFLs in general?
Asked By : Trap123
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/33903 3.2K people like this
