Is the union of 2 non context free languages always non context free?

Question

Let $L_1 = \{a^nb^nc^n\}$ and $L_2 = \{a^ib^jc^k \mid i\ne j\text{ or }j\ne k\}$ (which I think is a non Context free but I am not sure)

So, $L_1 \cup L_2$ will give $L_3 = \{a^*b^*c^*\}$ which is a CFG.

Is this correct?

Answer 1

Let $L$ be a non-context-free language over $\{0,1\}$. Then $0L \cup 1\Sigma^*$ and $0\Sigma^* \cup 1L$ are not context-free, but their union $\Sigma^+$ is context-free.

Answer 2

As you suspected, the union of two non context-free languages may be context-free.

For example, $\{a^nb^nc^n\mid n\ge0\}\cup\{a^nb^nc^m \mid m,n\ge 0,m\ne n\,\} = \{a^nb^nc^m\mid m,n\ge0\}$.

For a simpler example, $\{a^{n^2}\mid n\ge 0\}\cup\{a^{m}\mid m \text { is not a square}\} = \{a^{n}\mid n\ge 0\}$.

In fact, by a counting argument on countably infinity, for almost all languages $L$, both $L$ and its complement $\overline L=\Sigma^*\setminus L$ are non context-free (and even non context-sensitive), where $\Sigma$ is the (nonempty) alphabet. Their union, $\Sigma^*$ is context-free (and, actually, regular).

---

Your example is not correct since $L_3\setminus L_1 = \{a^nb^mc^k\mid n,m,k\ge0, n\ne m\}\cup \{a^nb^mc^k\mid n,m,k\ge0, m\ne k\}$ is a union of two context-free languages, hence also context-free.

Answer 3

$\Sigma^*$ is context free and its union with any language at all is $\Sigma^*$, which is still context-free.

If you want to consider questions about closure properties of languages, always start with things like $\emptyset$ and $\Sigma^*$, which are in any sane class of languages, and very often give give trivial counterexamples to false hypotheses about closure properties. For example, is the union of two non-regular languages always non-regular? No, because it's easy to come up with a language $L$ such that $L$ and $\overline{L}$ are non-regular, but we have $L\cup \overline{L}=\Sigma^*$, which is regular. And, if you wanted intersection instead, $L\cap\overline{L}=\emptyset$ and that's regular, too.