2
$\begingroup$

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?
$\endgroup$
  • 1
    $\begingroup$ What research have you done? Do you know what "undecidable" means? Do you know how to prove that a language is decidable or not? You ask "how can I prove this theorem" - what have you tried? How have you tried to prove it? Do you know how to prove that something is/isn't decidable? $\endgroup$ – D.W. Jul 18 '14 at 21:49
  • $\begingroup$ @D.W. Some. Yes. Yes. See above. By using known properties. Yes (same question as 2). How do these questions help? $\endgroup$ – polym Jul 19 '14 at 1:06
8
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ Is the intersection of two context-free languages then at least context-sensitive, or can it be just a decidable, but not context-sensitive language? $\endgroup$ – polym Jul 18 '14 at 21:07
  • 2
    $\begingroup$ @polym Context-free languages are context-sensitive, and context-sensitive languages are closed under intersection. So, yes, the intersection of two CF languages is context-sensitive. $\endgroup$ – babou Jul 18 '14 at 21:17
  • $\begingroup$ Ah right thanks. My mistake was not considering $CFL \subseteq CSL$ and the properties of CSL. $\endgroup$ – polym Jul 19 '14 at 1:26
  • $\begingroup$ Q1. Is this problem decidable: "Is the intersection of two context free languages also context free?" Q2. Does all questions asking if operation on two languages of same type, not closed under that operation, result in the language of the same type are undecidable? $\endgroup$ – anir123 Dec 22 '16 at 17:21
  • $\begingroup$ @Mahesha999 Comments can be used for clarification, not for new questions. So you should ask this in a new question. But you should make precise what you mean by the type of a language, and by an operation on two languages of the same type, if you want Q2 to make sense. $\endgroup$ – babou Dec 22 '16 at 20:41
5
$\begingroup$

Make sure that you understand what decidable means for a language $L$: it means that there is an algorithm that, given $x$, terminates and outputs either $x \in L$ or $x \notin L$ (correctly). It is easy to construct such an algorithm for the language $L = \emptyset$: it always returns $x \notin L$.

As babou mentions in their answer, while context-free languages are not closed under intersection, it is easy to decide whether $x \in L_1 \cap L_2$ for any context-free $L_1,L_2$:

  • First determine whether $x \in L_1$ and $x \in L_2$
  • If both are true:
    • return $x \in L_1 \cap L_2$
  • Otherwise:
    • return the converse.

As babou mentions, we only really use the fact that $L_1,L_2$ are themselves decidable.

$\endgroup$
  • $\begingroup$ So the empty language $L_{\emptyset}$ is decidable, because I can always say that $x \not\in L_{\emptyset}$ and my machine stops after telling me that? $\endgroup$ – polym Jul 18 '14 at 21:22
  • 1
    $\begingroup$ @polym Exactly. $\endgroup$ – Yuval Filmus Jul 18 '14 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.