# Intersection between context-free and context-sensitive language decidability [closed]

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ε, KavehDec 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.

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

## 1 Answer

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

• (It's also undecidable for a single context-sensitive language i.e. $L=\emptyset$) – sdcvvc Dec 26 '13 at 17:42
• 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 – Paul Dec 26 '13 at 23:48
• It seems to me this question is an assignment and is therefore off-topic for cstheory. – Kaveh Dec 27 '13 at 1:29