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_1capemptyset=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
