# can the union of regular languages be non-Context-Free

I came across the following statement which is supposedly true:

There exists an infinite set of regular languages, such that their union is not a CFL

it is explained this way: we'll define $$L_k = \{ 0^k1^k0^k \}$$

$$\bigcup_{i=1}^{\infty}$$ $$L_i = \left\{ 0^k1^k0^k \mid k \geq 1 \right\}$$

so that each language in the union only contains one string and therefore - regular, but their union is equivalent to: $$0^n1^n0^n$$ which is not CF.

on the other hand regular languages are closed under union, which means it'd be easy to prove inductively that the above union = regular language, since it consists only of regular languages.

and all regular languages are CF.

• @Skynet No. Induction is used to prove statements on every element of one specific infinite set: $\Bbb N$ Jan 29 at 18:24
Actually, every language $$L$$ on a finite alphabet is a countable union of regular languages. Just observe that all finite languages are regular and that $$L = \bigcup_{u \in L}\ \{u\}$$ Now, you can choose for $$L$$ not only a non-context-free language, but a non-context-sensitive or a non-recursively enumerable one if you wish.