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?
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.
