# Is the problem that intersection of two cfl is a cfl or not undecidable?

I am trying to use the computation histories argument to fit this. But I am unable to find this as yet.

• Probably. The techniques here are probably enough to prove this (if it's not there already!). – Yuval Filmus Nov 22 '16 at 23:06
• See also cs.stackexchange.com/q/15014/755 (your problem can be reduced to determining whether a context-sensitive language is context-free), cs.stackexchange.com/q/23056/755 (suggests looking at range concatenation grammars), and cs.stackexchange.com/q/23111/755. – D.W. Nov 23 '16 at 0:19
• @YuvalFilmus I could not find it in the linked note, but I guess the trick of Theorem 10 can be used. Given CFL $L_1$ and $L_2$ we can construct CFL $K_1$ and $K_2$ such that $K_1\cap K_2$ is context-free iff $L_1 \cap L_2$ is empty. – Hendrik Jan Nov 23 '16 at 2:06
• Is it correct to reduce $CFL_1\cap CFL_2=\emptyset$ to $CFL_1\cap CFL_2=CFL$ by putting $CFL=\emptyset$? Given that emptyness problem is undecidable, context free-ness problem will also become undecidable. Right? – anir Jan 11 '20 at 16:24