Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
If two regular languages $L_1$ and $L_2$ are both not context free languages then is $L_1 \cup L_2$ also not a context free?
I am aware that if $L_1$ and $L_2$ are context free languages then the language $L_1 \cap L_2$ is also context free but cannot quite connect the dots. If someone could help out that would be great.
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
First, note that CFL is not closed under intersection, contrary to what you've mentioned. For example: $$ L_1 = \{a^ib^ic^j|i,j \geq 0\}, \quad L_2 = \{a^ib^jc^j|i,j\geq 0\}. $$ We see that $L_1 \cap L_2 = \{a^ib^ic^i|i\geq0\}$, which is not CFL.
For your question, Take two languages $L_1, L_2$ which are not CFL. Let $$ \begin{align*} L'_1 &= \{0x|x \in L_1 \} \cup \{1x|x \in \Sigma^*\}, \\ L'_2 &= \{1x|x \in L_2 \} \cup \{0x|x \in \Sigma^*\}, \\ \end{align*} $$ which are both not CFL. It's easy to see that $L'_1 \cup L'_2 = \Sigma^*$, which is CFL (as it is a regular language).
