# Infinite Union of non-regular languages

Is infinite union of non-regular languages $L_i$ that form a chain such that $L_i\subseteq L_{i+1}$ always non-regular?

Or is there a possibility that it be ever regular?

Is there an easy way to see this?

• I'm certain we have a duplicate of this. – Raphael Nov 3 '15 at 19:04
• @Raphael The question has changed. – Yuval Filmus Nov 3 '15 at 20:24
• Consider $L_i=\{w\in\{a,b\}^*\ |\ |w|_a-|w|_b\le i\}$. – Klaus Draeger Nov 3 '15 at 20:54

## 1 Answer

Let $L$ be a non-regular language over $\Sigma$, and let $w_1,w_2,\ldots$ be an enumeration of $\Sigma^*\setminus L$. Define $L_i = L \cup \{ w_j : j \geq i \}$. Each $L_i$ is non-regular (why?), $L_i \subset L_{i+1}$, and $\bigcup_i L_i = \Sigma^*$.

• So in general kleene star of a non-regular language is regular? – T.... Nov 3 '15 at 20:04
• No, for example $\{0^n1^n:n\geq0\}^*$ is not regular (why?). – Yuval Filmus Nov 3 '15 at 20:05
• Since it contains $0^n1^n0^m1^m$ – T.... Nov 3 '15 at 20:08
• Since it contains $\mathsf{only}$ strings of form $0^n1^n0^m1^m\dots$? – T.... Nov 3 '15 at 20:18
• Pumping lemma? Take $xyz = 0^n1^n$ with $y=0$ and pump $y$? – T.... Nov 3 '15 at 20:26