[Solved]: Can an intersection of two context-free languages be an undecidable language?

Problem Detail: 

I'm trying to prove that

$\exists L_1, L_2 : L_1$ and $L_2$ are context-free languages $\land\;L_1 \cap L_2 = L_3$ is an undecidable language.

---

I know that context-free languages are not closed under intersection.

This means that I can produce an $L_3$, which is undecidable.

An example would be $L_1 = \{a^n | n \in \mathbb{N}\} \cap L_2 = \{0\} = \emptyset$.

• Is this a correct proof?
• If not, how can I prove this theorem?
• Is the empty language decidable?

Asked By : polym

Answered By : babou

Context-free languages are decidable, and decidable languages are closed under intersection.

So, though the intersection of two CF languages may not be CF, it is decidable.

Remarks on your example:

• $\emptyset=\{\}\neq$ $\{0\}$

• $L_1\cap\emptyset=\emptyset$ which is context-free.

• You cannot prove your claim, because it is wrong

• the empty language is decidable: the answer is always "no, this string is not in the empty set".

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/28531