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?

  • $\begingroup$ Your $L_2$ is context-free. Your gut instinct is right; look for even simpler $L_1 \cup L_2$! $\endgroup$
    – Raphael
    Commented Apr 15, 2018 at 9:50

1 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^*$.

  • $\begingroup$ Thanks, but the sigma is {a,b,c}... more complicated I guess $\endgroup$
    – koral
    Commented Apr 15, 2018 at 10:40
  • $\begingroup$ Not really. This example generalizes to any alphabet. $\endgroup$ Commented Apr 15, 2018 at 10:41
  • $\begingroup$ so if I take for example: L= {a^nb^nc^mb^m}, and L1={aL union bsigma* union csigma* union epsilon}, L2= {bL union asigma* union csigma* union epsilon} its the same? $\endgroup$
    – koral
    Commented Apr 15, 2018 at 11:14
  • $\begingroup$ I'll let you figure out how to generalize this to larger alphabets. There are many ways. You have indicated one of them. $\endgroup$ Commented Apr 15, 2018 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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