# Union of infinitely many regular languages [duplicate]

I need to prove or disprove the following statement.

If $$A_n ⊆ \Sigma^*$$ is regular for each $$n \in \mathbb{N}$$ then $$\bigcup\limits_{n=0}^{\infty} A_n$$ is regular.

I know that if two languages are regular, then the union of the languages is also regular. I don't think that really applies to this problem, because it's the union of every $$n \in \mathbb N$$. Also, to help with my understanding with the definitions, is $$A_n$$ a language or an alphabet, since it's a subset of $$\Sigma^*$$?

## marked as duplicate by xskxzr, Evil, Community♦Feb 13 at 21:57

Is $$A_n$$ a language or an alphabet, since it's a subset of $$\Sigma^*$$?

A member of the alphabet, $$\Sigma$$ is called a symbol or a letter.
A member of $$\Sigma^*$$ is called a string or a word, which is a finite sequence of symbols or letters.
A subset of $$\Sigma^*$$ is called a language.

If $$A_n\subseteq \Sigma^*$$ is regular for each $$n\in\Bbb N$$ then $$\bigcup\limits_{n=0}^{\infty} A_n$$ is regular.

As you suspected, this is not true. For example, let $$A_n=\{a^nb^n\}$$. Then $$\bigcup\limits_{n=0}^{\infty} A_n$$ is the well-known non-regular language of words with equal number of $$a$$'s and $$b$$'s. Infinity should indeed be treated carefully.

Exercise 1. Give an example of a non-regular language $$L$$ over unary alphabet such that $$L=\bigcup\limits_{n=0}^{\infty} A_n$$ where $$A_n$$ is a regular language for all $$n$$.

Exercise 2. Let $$L$$ be any language. Then $$L=\bigcup\limits_{n=0}^{\infty} A_n$$ for some regular language $$A_n$$.

• My only question is I thought we were assuming the language to be regular? I thought {a^n b^n} was not regular, so we aren't even starting with the assumption that An is regular. – James Swanson Feb 13 at 20:31
• $A_1=\{ab\}$. $A_2=\{a^2b^2\}$. $A_3=\{a^3b^3\}$. And so on. Each $A_n$ is a language that has only one word. Their union, $\{ab, a^2b^2, a^3b^3, \cdots\}=\{a^nb^n\mid n\in \Bbb N\}$ is not regular. – Apass.Jack Feb 13 at 21:14
• Ok i misinterpreted the question, so its to assume that every A(sub n) is regular, which I guess is very obvious since they would all be finite, because they are singletons. – James Swanson Feb 13 at 21:43
• You can use $A_n$ to show $A_n$. – Apass.Jack Feb 13 at 21:53
• Yes, as you said, it is very obvious indeed. Please accept the answer so that we may call an end of the question. – Apass.Jack Feb 13 at 21:56