Union of regular languages that is not regular

Question

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.

Answer 1

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.

Answer 2

For your second question, consider the languages defined by $$ M_n = \{a^{k^2}\mid 1\le k \le n\}\cup\{a^j\mid j\ge(n+1)^2\} $$ Observe that for any $n\ge 1$, $M_n$ is regular, since (1) the left set is finite and hence regular, (2) the right set is denoted by the regular expression $a^naa^*$ so is regular, and (3) regular languages are closed under finite unions, as you already know.

It's not too difficult to show that for any integer $n\ge 1$ we have $M_{n+1}\subseteq M_n$ and hence $M_n\cap M_{n+1} = M_{n+1}$ so inductively we have $$ \bigcap_{i=0}^n M_i = M_n $$ (which we don't actually need here, but it's too pretty to leave out).

Now observe that $M_n$ doesn't contain $a^{n^2+1},a^{n^2+2}, \dotsc, a^{(n+1)^2-1}$, so none of these strings will be in the full intersection. As a consequence we'll have $$ \bigcap_{i=0}^\infty M_i = \{a^{n^2}\mid n\ge 1\} $$ which is known not to be a regular language. (If you didn't know this fact, it's in many theory texts and the proof is well worth the effort of reading.)

Answer 3

If you do the Union of infinitely many Unit Sets, you can make any language (well, at least, any r.e. language, because if it is undecidable, you cannot specify the list of all its strings). For example, the union of unit sets where each contains a different palindrome string over {a, b}, gives as result the palindrome language (context-free): this is $\{\epsilon\} \bigcup \{a\} \bigcup \{b\} \bigcup \{aa\} \bigcup \{bb\} \bigcup \{aaa\} \bigcup \{aba\} \bigcup \{bab\} \bigcup \{bbb\} \bigcup \ ... $

You can do something similar with intersection, making infinitely many sets where each is $ \Sigma^* - \{ p_i \}$ , where $p_i$ is the $i$th palindrome word, resulting the language of all not palindromes words (complement of palindrome language, non-regular).

Answer 4

Why choose complicated regular languages to show that regular sets are not closed under infinite union? Singleton languages are enough to show that any RE language is an infinite union of regular sets.

Take any recursively enumerable language $L$. Each string $w\in L$ has an enumeration index $i=index(w)$. Let $L_i=\{w\mid i=index(w)\}$. Every $L_i$ is a singleton set, hence regular. But $L =\bigcup_{i=1}^{\infty}L_i\;$ is RE.

Similarly, defining $M_i=\Sigma^*\setminus L_i$, we have the sets $M_i$ which are regular as complements of a singleton set. Then $\bigcap_{i=1}^{\infty}M_i= \Sigma^*\setminus L\;$ which is the complement of $L$, hence co-RE. And that can be achieved with any co-RE set.

Hence any recursive language is an infinite union of regular sets, and also an infinite intersection of regular sets (not the same ones, but their complements:).

Infinity is full of surprises, and what is true for arbitrarily large values may not be true at infinity.