1

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.

Evgenii.Balai
  • 299
  • Hint: The following should work. Take your favourite non-regular language, call it $L_1$. Enumerate the words that are not in the language, and add them one at a time. The union is everything, very regular. – André Nicolas Feb 07 '13 at 07:32
  • Thank you. So the answer yes "it may be regular". (Of course we can take all L_i equal to some non-regular language and it will lead us to a non-regular union). – Evgenii.Balai Feb 07 '13 at 07:43

1 Answers1

2

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.

  • Very interesting idea, thanks. I think we should also mention that the set of all strings is countable (so L_i must be some non-regular language unioned with i-th string). – Evgenii.Balai Feb 07 '13 at 07:34