<p>The problem is undecidable even for two context-free languages. See for instance <a href="http://www.cs.wcupa.edu/~rkline/fcs/other-undecidable.html" rel="nofollow">this page</a> for a short proof.</p>

CC BY-SA 3.0
2013-12-26T17:42:06.173Z
(It's also undecidable for a single context-sensitive language i.e. $L=\emptyset$)
sdcvvc
CC BY-SA 3.0
2013-12-26T23:48:13.470Z
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
CC BY-SA 3.0
2013-12-27T01:29:10.697Z
It seems to me this question is an assignment and is therefore off-topic for cstheory.
Kaveh
CC BY-SA 3.0
2013-12-26T17:10:34.177Z
2013-12-26T17:10:34.177Z
J.-E. Pin
<p>I'm trying to find a formal proof of the following fact:</p>

<p>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$)</p>

<p>Some suggestions for the proof? Thanks</p>

CC BY-SA 3.0
2013-12-27T01:27:45.347Z
This seems to be an undergraduate assignment level question and therefore is more suitable for [cs.se].
Kaveh
CC BY-SA 3.0
2013-12-28T16:22:27.830Z
This question has been [reposted on Computer Science](http://cs.stackexchange.com/questions/19326/intersection-between-context-free-and-context-sensitive-language-decidability).
Gilles 'SO- stop being evil'
<cc.complexity-theory><computability><automata-theory><context-free><decidability>
Intersection between context-free and context-sensitive language decidability
Paul
# Intersection between context-free and context-sensitive language decidability

(Asked by: username_0 on 2013-12-26)

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

**Tags:** cc.complexity-theory, computability, automata-theory, context-free, decidability

> **Comments:**
> **username_1**: This seems to be an undergraduate assignment level question and therefore is more suitable for [cs.se].  
> **username_2**: This question has been [reposted on Computer Science](http://cs.stackexchange.com/questions/19326/intersection-between-context-free-and-context-sensitive-language-decidability).  

---

## 1 answers

### Answer by username_3 on 2013-12-26. Score: 4

The problem is undecidable even for two context-free languages. See for instance [this page](http://www.cs.wcupa.edu/~rkline/fcs/other-undecidable.html) for a short proof.

> **Comments:**
> **username_4**: (It's also undecidable for a single context-sensitive language i.e. $L=\emptyset$)  
> **username_0**: 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  
> **username_1**: It seems to me this question is an assignment and is therefore off-topic for cstheory.  

---

