Solution Verification: There exists an infinite set of different irregular languages such that their union is a regular language.

Question

Prove or disprove: There exists an infinite set of different irregular languages such that their union is a regular language.

My intuition led me to try to disprove, since if I had a set that is built by union of infinite different irregular languages, the automat that I need to build that accepts that set should accept every set that builds that union, and so I think that that automat doesn't exist.

My Attempt to Disprove:

Let's denote the set $L$ as an infinite union of irregular languages.
Assume by contradiction that $L$ is regular, that means there exists an automat $A$ such that $L(A)=L$.
Since $L$ is an infinite union of irregular languages then we can write: $$L=\bigcup_{i\in \mathbb{N}}L_i$$ Where $L_i$ is irregular for each $i\in\mathbb{N}$.

Let's check if there exists $A$ such that $L \subseteq L(A)$ first. Let $x\in L=\bigcup_{i\in \mathbb{N}}L_i$, that means $x\in L_1$ or $x\in L_2$ or ... $x\in L_i$.
Without loss of generality, let's say $x\in L_i$, but $L_i$ is an irregular language, which by definition means that there doesn't exist an automat $B$ such that $L(B)=L_i$, so I can infer that there is no automat $A$ such that $x\in L(A)$ which means $L\nsubseteq L(A)$ so $L\ne L(A)$. which is a contradiction.

Possible mistakes I thought of and struggling to approve:

1. If there isn't an automat $B$ such that $L(B)=L_i$. then if $x\in L_i$, then can I really infer that $x\notin L(B)$? what if $x$ is in both of them even if they aren't equivalent?
   
2. I'm not sure that writing $L$ as I did is the correct way of expressing what's written in the question.

Answer 1

Well, since no one else answered, I might as well.

Let’s check if there exists $A$ such that $L \subseteq L(A)$.

There is. There always is. The full language of all strings is regular. It’s accepted by an automaton with one state, both initial and terminal, and a looping arrow for every symbol in the alphabet.

…which by definition means that there doesn't exist an automat $B$ such that $L(B)=L_i$, so I can infer that there is no automat $A$ such that $x\in L(A)$ which means…

Here’s the false implication; your concern number 1 was well-founded. Any single string can be accepted by an automaton. Naturally, there’s the automaton that accepts everything as outlined above. But also, any language containing a single word (any word you like) is regular.

So, for example, $aabb \in \{a^nb^n : n \in \Bbb{N}\}$, but it’s also accepted by many automata. For example, consider an automaton with $5$ states, $1, 2, 3, 4, 5$, where $1$ is initial and $5$ is terminal. Let an $a$ arrow connect $1$ to $2$ and $2$ to $3$, while a $b$ arrow connect $3$ to $4$ and $4$ to $5$. Such an automaton accepts $aabb$ and only $aabb$.

You might be able to see how this extends to any word: make one state for every symbol in the word, plus an extra terminal one, and let the arrows from one state to the next be the next symbol in the word. So, indeed, any language consisting of a single word is regular.

What I’m saying is, you cannot determine by looking at a single word in a language (or even finitely many words) if a language is regular or not.

---

Let me expand the comments under the question, which provide the actual solution to this exercise:

You are, as you said in the comments, familiar with $\{a^n b^n : n \in \Bbb{N}\}$ (or alternatively, $\{a^i b^j : i = j\}$) being irregular. Let’s call it $L_0$. For $n \in \Bbb{Z}$, let $$L_n = \{a^i b^j : i - j = n\}.$$ I claim that $L_n$ is irregular.

The standard way to do this kind of thing is using pumping lemma, and indeed this is the way $L_0$ is typically proven to be irregular. However, we can also prove this using operations known to preserve regular languages:

Suppose $M_1$ and $M_2$ are two regular languages. Then $M_1 \cup M_2$ is regular.

Sketch proof: It’s easier if you know about non-deterministic automata, and how they only accept regular languages. All you do is merge the initial states of the two automata that accept $M_1$ and $M_2$, and keep the arrows coming from it to the two different automata. Because both automata could have an arrow with the same label coming from their initial state, this could make the automaton non-deterministic.

Using the fact that languages consisting of a single word are regular, and the empty language is regular, this means that finite languages are regular too.

Suppose $M_1$ and $M_2$ are regular. Then $M_1M_2 = \{w_1w_2 : w_1 \in M_1, w_2 \in M_2\}$ is regular.

Sketch proof: If $A_1$ and $A_2$ are automata for $M_1$ and $M_2$, turn each accepting state of $M_1$ into the initial state of a copy of $A_2$, so that once $A_1$ accepts the first part of the word, then $A_2$ can judge the remainder of the word. Once again, this may turn out non-deterministic, but this isn’t a problem.

So, using these results, note that, for $n \in \Bbb{N}$, the singleton languages $\{a^n\}$ and $\{b^n\}$ (note: $n$ is a fixed natural number, and the sets have only one element) are regular. So, if I assume that $L_n$ or $L_{-n}$ is regular for some $n \in \Bbb{N}$ (for the sake of contradiction), then I may conclude that one of the concatenations $L_n\{b^n\}$ or $\{a^n\}L_{-n}$ are regular. Note that $$L_n\{b^n\} = \{a^n\}L_{-n} = \{a^k b^k : k \ge n\},$$ so in either case, $\{a^k b^k : k \ge n\}$ is regular.

Now, note that $$L_0 = \{a^k b^k : k \in \Bbb{N}\} = \{a^k b^k : k \ge n\} \cup \{\varepsilon, ab, a^2b^2, a^3b^3, \ldots, a^{n-1}b^{n-1}\},$$ which is a finite union of a regular language with a finite language (which is therefore regular), so in total, we get $L_0$ is regular. This contradicts your knowledge about $L_0$ being an irregular language. Thus, my assumption that $L_n$ or $L_{-n}$ is regular for some $n \in \Bbb{N}$ is false. So, $L_n$ is irregular for all $n \in \Bbb{Z}$.

(Of course, if you’re attempting this exercise at the right time in your study, you won’t have to do this much proof!)

We have $$\bigcup_{n \in \Bbb{Z}} L_n = \{a^ib^j : i,j \in \Bbb{N}\}.$$ Why? Certainly any $a^ib^j \in L_n$, for any given $n \in \Bbb{Z}$, takes the correct form, so we definitely have $\subseteq$. On the other hand, given $a^ib^j$ in the right hand side, $i - j \in \Bbb{Z}$, so let it be $n$. Then $a^i b^j \in L_n$, giving us $\supseteq$.

The language on the right is regular. It is accepted by an automaton with two states, both accepting, the initial one having a looped $a$ arrow, plus a $b$ arrow to the next state. The next state also has a looping $b$ arrow. So, we have our counterexample.

Answer 2

There exists an infinite set of different irregular languages such that their union is a regular language, even on a one-letter alphabet. Indeed, let $L = \{a^{n^2} \mid n \geqslant 0\}$ and $L_n = L \cup \{a^n\}$. Then each $L_n$ is non-regular, but $$ \bigcup_\text{$n$ is a non-square integer} L_n = a^* $$ is regular. Moreover, if $n$ and $m$ are two distinct non-square integers, then $L_n \neq L_m$.