0
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ This is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. What have you tried? Have you tried working out a few examples? $\endgroup$ – D.W.♦ Mar 18 '14 at 22:14
  • 1
    $\begingroup$ Also, the question has probably been answered before. There are quite obvious counter-examples. Important: CFL is not closed against intersection! $\endgroup$ – Raphael♦ Mar 19 '14 at 0:06
6
$\begingroup$

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).

| cite | improve this answer | | | | |
$\endgroup$

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