I am trying to use the computation histories argument to fit this. But I am unable to find this as yet.
$\begingroup$
$\endgroup$
-
2$\begingroup$ Probably. The techniques here are probably enough to prove this (if it's not there already!). $\endgroup$ – Yuval Filmus Nov 22 '16 at 23:06
-
$\begingroup$ 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. $\endgroup$ – D.W.♦ Nov 23 '16 at 0:19
-
$\begingroup$ @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. $\endgroup$ – Hendrik Jan Nov 23 '16 at 2:06
-
$\begingroup$ 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? $\endgroup$ – anir Jan 11 at 16:24
