Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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^*$?
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$.
