I'm trying to find a formal proof of the following fact:

Given a context-free language, say $L_1$, and a context-sensitive language, say $L_2$, it is NOT decidable if their intersection is empty ($L_1 \cap L_2 = \emptyset$)

Some suggestions for the proof? Thanks


closed as off-topic by Jeffε, Kaveh Dec 28 '13 at 21:31

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Jeffε, Kaveh
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ This seems to be an undergraduate assignment level question and therefore is more suitable for Computer Science. $\endgroup$ – Kaveh Dec 27 '13 at 1:27
  • 2
    $\begingroup$ This question has been reposted on Computer Science. $\endgroup$ – Gilles Dec 28 '13 at 16:22

The problem is undecidable even for two context-free languages. See for instance this page for a short proof.

  • 1
    $\begingroup$ (It's also undecidable for a single context-sensitive language i.e. $L=\emptyset$) $\endgroup$ – sdcvvc Dec 26 '13 at 17:42
  • $\begingroup$ Ok, let's suppose that I know that is undecidable for a single context-sensitive language. I want to show that the intersection problem is undecidable too, without using the PCP fact (and directly from CF^CS, not CF^CF). Just a logic or languages proof. How do you do that? I know it's quite obvious, but I need a rigorous proof by contradiction, starting from the fact that I know it's undecidable for every c.s. language. thank you $\endgroup$ – Paul Dec 26 '13 at 23:48
  • 1
    $\begingroup$ It seems to me this question is an assignment and is therefore off-topic for cstheory. $\endgroup$ – Kaveh Dec 27 '13 at 1:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.