[Solved]: Reducing context-free languages with polynomial-time reductions

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: n\geq 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

 Download Related Notes/Documents