3
$\begingroup$

Context-free languages are not closed under intersection.

Suppose $L_1, L_2 \in CF \setminus REG$ (i.e., $L_1,L_2$ are context-free but not regular).

Are there well-known theorems (and/or whole papers/research topics) that try to shape the sufficient/necessary conditions for $L_1,L_2$ to make $L_1 \cap L_2$ context free?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ The background of this question is that it is undecidable whether the intersection of two context-free languages is context-free. $\endgroup$ – John L. May 20 '19 at 19:14
  • $\begingroup$ You can probably generalize the example in this answer. We can ask more generally, which context-free language are such that their intersection with a context-free language is always context-free. $\endgroup$ – Yuval Filmus May 21 '19 at 8:41
  • $\begingroup$ A related question, language whose intersection with a CFL is always a CFL. $\endgroup$ – John L. Jun 10 '19 at 9:22

Your Answer

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

Browse other questions tagged or ask your own question.