Union of regular languages that is not regular

Question Detail: 

I've come across that question : "Give examples of two regular languages which their union doesn't output a regular language. "

This is pretty shocking to me because I believe that regular languages are closed under union. Which means to me that if I take two regular languages and union them, I must get a regular language.

And I think I understand the proof of that : In my words, if the languages are regular, then there exist automatas that recognize them. If we take all the states (union), and we add a new state for the entry point, and we modify the transition function for the new state with epsilon, we are ok. We also show that there exist a path from every state etc.

Can you tell me where I'm wrong, or maybe another way to approach the question.

Source of the question, exercise 4, in french.

Also, the same question is asked with the intersection.

Asked By : Dave

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30457

Answered By : Luke Mathieson

There's a significant difference between the question as you pose it and the question posed in the exercise. The question asks for an example of a set of regular languages $L_{1}, L_{2}, \ldots$ such that their union $$ L = \bigcup_{i=1}^{\infty}L_{i} $$ is not regular. Note the range of the union: $1$ to $\infty$. Regular languages are closed under finite union, and the proofs runs along the lines that you sketch in the question, however this falls apart under infinite union. We can show this by taking $L_{i} = \{0^{i}1^{i}\}$ for each $i$ (with $\Sigma = \{0,1\}$). The infinite union of these languages of course gives the canonical non-regular (context-free) language $L = \{0^{i}1^{i}\mid i \in \mathbb{N}\}$.

As an aside, we can see easily where the normal proof fails. Imagine the the same construction where we add a new start state and $\varepsilon$-transitions to the old start states. If we do this with an infinite set of automata we have build an automata with an infinite number of states, obviously contradicting the definition of a finite automata.

Lastly, I'm guessing the confusion may arise from the phrasing of the original question, which starts "Donner deux exemples des suites de langages...", which is (roughly, my French is a bit rusty, but externally verified!) "Give two examples of sequences of languages...", rather than "Give two examples of languages...". An incautious reading may mistake the second for the first though.