3
$\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?
Improve this question
$\endgroup$
2
  • 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. ♦
    Commented Jul 18, 2014 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
    Commented Jul 19, 2014 at 1:06

2 Answers 2

Reset to default
9
$\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".

Improve this answer
$\endgroup$
11
  • $\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
    Commented Jul 18, 2014 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
    Commented Jul 18, 2014 at 21:17
  • $\begingroup$ Ah right thanks. My mistake was not considering $CFL \subseteq CSL$ and the properties of CSL. $\endgroup$
    – polym
    Commented Jul 19, 2014 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$
    – Mahesha999
    Commented Dec 22, 2016 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
    Commented Dec 22, 2016 at 20:41
6
$\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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jul 18, 2014 at 21:22
  • 1
    $\begingroup$ @polym Exactly. $\endgroup$
    – Yuval Filmus
    Commented Jul 18, 2014 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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