Is the union of two non-regular context-free languages always non-regular? I had this question in my HW:


  Prove of disprove: If $L_1$ and $L_2$ are non-regular context free languages then $L_1 ∪ L_2$ is not regular.


My intuition is that it is wrong. I thought about the following two languages:


$L_1 = \{a^ib^jc^k : 0 \leq i \leq j \leq k\}$ and
$L_2 = \{a^ib^jc^k : j&lt;i \lor j&gt;k\}$.


The union of these two languages is $a^*b^*c^*$ which is regular, but I didn't succeed to prove that $L_2$ is not a CFL (tried with the pumping lemma and stuck in the case that $vxy$ contains two types of letters).

Am I right with my intuition? if do so, how can I prove that $L_2$ isn't a CFL, or which other two languages disprove this claim?
Let $L$ be any non-regular context-free language over $\{0,1\}$, for example $\{ 0^n 1^n : n \geq 0 \}$. Take
$$
\begin{align*}
L_1 &amp;= 0L \cup 1\Sigma^* \cup \{\epsilon\}, \\
L_2 &amp;= 1L \cup 0\Sigma^* \cup \{\epsilon\}.
\end{align*}
$$
Then $L_1$ and $L_2$ are also non-regular context-free (exercise), but $L_1 \cup L_2 = \Sigma^*$.