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

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?

• Welcome to Computer Science! You can use LaTeX to typeset various formulas. I edited to show you how; we also have a brief tutorial. – John L. Nov 1 '18 at 3:07
• The title reads "is ... non context-free" while the body reads " ... is a CFG". Are you saying you have answered your question in the title with the counterexample in the body? – John L. Nov 1 '18 at 3:18
• What do you mean by $i\neq j\neq k$? – xskxzr Nov 1 '18 at 3:45
• @Apass.Jack - is my counterexample correct?? Though I am not sure about L2={aibjck∣i≠j≠k} being a non CFL. – Achilles Nov 1 '18 at 3:56
• @xskxzr - exponent values of i, j and k will never be same at a time. Hence, at-least 1 value will be different than the other. – Achilles Nov 1 '18 at 3:59

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.

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.

• Thank you. These examples make more sense. – Achilles Nov 2 '18 at 2:38

$$\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.