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^*$?


1 Answer 1


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$.

  • $\begingroup$ 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. $\endgroup$ Feb 13, 2019 at 20:31
  • $\begingroup$ $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. $\endgroup$
    – John L.
    Feb 13, 2019 at 21:14
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 13, 2019 at 21:43
  • $\begingroup$ You can use $A_n$ to show $A_n$. $\endgroup$
    – John L.
    Feb 13, 2019 at 21:53
  • $\begingroup$ Yes, as you said, it is very obvious indeed. Please accept the answer so that we may call an end of the question. $\endgroup$
    – John L.
    Feb 13, 2019 at 21:56

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