# Union of two non-context-free languages

Let L1 = L2 union L3 find values such that L1 is context free and L2 and L3 are not.

So far I have: L1 = $a^nb^n$ L2 = $a^*b^*$ L3 = $a^+b^+$

Is this acceptable?? Since L2 covers everything including epsilon and L3 is the same but does not include epsilon?

I know L2 is regular so I guess that is also not a CFL. Another problem is that the a's and b's aren't linked in L2 and L3, so either one can always have more a's than b's and vice versa.

• Every regular language is also a context-free language. – kntgu May 13 '18 at 6:35
• There are two problems with your example: first, $L_2$ and $L_3$ are context-free; and second, $L_2 \cup L_3 \neq L_1$. You need to find a different example. – Yuval Filmus May 13 '18 at 8:00

Hint. For any language $L$, $$A^* = L \cup (A^* - L).$$ Now, choose an appropriate language $L$ to solve your problem.
Here is another construction: for every language $L$ over $\{0,1\}$, $$(0L \cup 1\Sigma^*) \cup (1L \cup 0\Sigma^*) = \Sigma^+.$$