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

  • 2
    $\begingroup$ Probably. The techniques here are probably enough to prove this (if it's not there already!). $\endgroup$ Commented Nov 22, 2016 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.
    Commented Nov 23, 2016 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$ Commented Nov 23, 2016 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$
    – RajS
    Commented Jan 11, 2020 at 16:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.