# How can the union of two 'context-free but not regular' languages be regular?

I cannot understand how the union of two languages which are context-free but not regular, can result in a regular language:

If $$L_1$$ and $$L_2$$ are 'context-free but not regular' languages, defined over the same alphabet $$Σ$$ then, the union $$L_1∪L_2$$ can be a regular language.

I can't find an example to prove that this statement is true because by definition the context-free languages are closed under union operation.

Could someone please provide an example?

• Yes, the result will be context free. Nobody cares. Is it regular though? Some context free languages are, some are not. Jul 24, 2019 at 19:27

Let $$L$$ be a context-free but not regular language over $$\{0,1\}$$ such that its complement language $$\overline L$$ is also context-free. Then $$\overline L$$ is not regular and $$L\cup\overline L=\Sigma^*$$ is regular.

In particular, let $$L=\{a^nb^n\mid n\in\Bbb N\}$$.

The previous example requires you to verify that both $$L$$ and $$\overline L$$ are context-free. Here is an example with less burden.

Let $$\Sigma=\{a,b,c,d\}$$. Let $$F_1$$ be a context-free but not regular language over $$\{a,b\}$$. Let $$F_2$$ be a context-free but not regular language over $$\{c,d\}$$. Then both $$F_1\cup\{c,d\}^*$$ and $$\{a,b\}^*\cup F_2$$ are context-free but not regular. The union of them, $$\{a,b\}^*\cup\{c,d\}^*$$ is regular.

In particular, Let $$F_1=\{a^nb^n\mid n\in\Bbb N\}$$ and $$F_2=\{c^nd^n\mid n\in\Bbb N\}$$.

Exercise 1. If $$R$$ is a regular language and $$F$$ is context-free but not regular such that $$R\setminus F$$ is context-free, then $$F\cup (R\setminus F)$$ is a desired example. Show that we can take $$R=a^*b^*$$ and $$F=\{a^nb^n\mid n\in\Bbb N\}$$.

Exercise 2. If $$L_1$$ and $$L_2$$ are 'context-sensitive but not context-free' languages, defined over the same alphabet $$Σ$$ then, the union $$L_1\cup L_2$$ can be a context-free language. In fact, the union $$L_1\cup L_2$$ can be a regular language as well.

• Here is another general construction. Let $\Sigma=\{a,b\}$. Let $L$ be a non-regular context-free language over $\Sigma$. Let $L_a = \{\epsilon\}\cup aL \cup b\Sigma^*$ and $L_b = \{\epsilon\}\cup a\Sigma^*\cup bL$. Then both $L_a$ and $L_b$ are non-regular context-free. $L_a \cup L_b = \Sigma^*$. Jul 25, 2019 at 21:06