Question about infinite union of non-regular languages

605 Views Asked by At

If none of the languages $L_1$,$L_2$,... is regular, and $L_i \subseteq L_{i+1}$ for each i, is $\bigcup_{n=1}^\infty L_i$ regular?

I guess the answer is no for any given languages, but I cannot formulate my arguments properly.

Thank you for the help.

1

There are 1 best solutions below

1
On BEST ANSWER

Let $L$ be a language that is not regular. Let $s$ be any string not in $L$. I claim that the language $L \cup \{ s \} $ is also not regular.

By adding in all strings not in $L$ one at a time, you get a nested union of non-regular languages whose union consists of all strings, and is therefore regular.

So no, you cannot conclude that the nested union of non-regular languages is also non-regular.