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$ Oct 10, 2013 at 2:42

1 Answer 1


The intersection could be empty.

  • $\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, 2013 at 23:15

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.