Can $L$ be regular language if it is a union of infinitely many regular languages $L_1,L_2,L_3,...$ over the same alphabet?

2.1k Views Asked by At

Can $L$ be regular language if it is a union of infinitely many regular languages $L_1,L_2,L_3,...$ over the same alphabet ?

(a) can $L$ be regular ?

(b) Is $L$ always regular ?

I want to make sure my logic is right. I am saying that the answer to both question is wrong because we will need construct FA $M$ that recognizes the union of the languages but since we have infinite number of states we can't construct M with infinite number of states.

2

There are 2 best solutions below

4
On BEST ANSWER

$L$ certainly can be regular. Let $\Sigma$ be any finite alphabet, and let $L=\Sigma^*$; $L$ is countably infinite, so we can enumerate it as $L=\{w_n:n\in\Bbb Z^+\}$. For $n\in\Bbb Z^+$ let $L_n=\{w_n\}$; the language $L_n$ is finite, so it’s certainly regular. The language $\Sigma^*$ is also regular, and clearly $\Sigma^*=\bigcup_{n\in\Bbb Z^+}L_n$.

On the other hand, it need not be: the same reasoning shows that every infinite language is a union of infinitely many regular languages, and there are certainly infinite languages that are not regular.

1
On

Your reasoning is heuristic, but certainly not any convincing reasoning. Firstly, of course the union of infinitely many regular languages can be regular. For instance, if all the languages are the same (but you can also come up with explicit examples which are less trivial).

Think about what you actually need to do in order to show, e.g., that the second assertion is incorrect. You will have to demonstrate regular languages $L_i$ (and prove they are regular) such that the union is a language known (or prove it!) to be not regular. You must provide these details for an actual proof.