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 Apr 15 '18 at 9:50

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

| cite | improve this answer | |
  • $\begingroup$ Thanks, but the sigma is {a,b,c}... more complicated I guess $\endgroup$ – koral Apr 15 '18 at 10:40
  • $\begingroup$ Not really. This example generalizes to any alphabet. $\endgroup$ – Yuval Filmus Apr 15 '18 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 Apr 15 '18 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$ – Yuval Filmus Apr 15 '18 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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