Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 7 '13 at 7: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 7 '13 at 7:43

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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 7 '13 at 7:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.