Assume two languages $L_1$ and $L_2$, both of which are non-context-free.

Let $L = L_1 \cap L_2$. Could $L$ be context-free?

  • 1
    $\begingroup$ It's more interesting to ask whether the intersection of two context-free languages is context-free (though the answer is still negative). The union of two context-free languages is always context-free. So the only case remaining is the union of two non-context-free languages. What do you think, is it always non-context-free? $\endgroup$ – Yuval Filmus Oct 10 '13 at 2:42

The intersection could be empty.

| cite | improve this answer | |
  • $\begingroup$ +1 - it's funny how the trivial cases often help us more than one might expect, isn't it. $\endgroup$ – G. Bach Oct 9 '13 at 23:15

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.