-2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 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.