Is the union of two non-regular context-free languages always non-regular?

Question

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<i \lor j>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?

Answer 1

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 &= 0L \cup 1\Sigma^* \cup \{\epsilon\}, \\ L_2 &= 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^*$.