1
$\begingroup$

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?

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

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, but the sigma is {a,b,c}... more complicated I guess $\endgroup$ 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$ 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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.