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?
$\begingroup$
$\endgroup$
1
-
4$\begingroup$ Consider $L_i=\{w\in\{a,b\}^*\ |\ |w|_a-|w|_b\le i\}$. $\endgroup$– Klaus DraegerNov 3, 2015 at 20:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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^*$.
answered Nov 3, 2015 at 19:50
-
$\begingroup$ So in general kleene star of a non-regular language is regular? $\endgroup$– TurboNov 3, 2015 at 20:04
-
$\begingroup$ No, for example $\{0^n1^n:n\geq0\}^*$ is not regular (why?). $\endgroup$ Nov 3, 2015 at 20:05
-
-
$\begingroup$ Since it contains $\mathsf{only}$ strings of form $0^n1^n0^m1^m\dots$? $\endgroup$– TurboNov 3, 2015 at 20:18
-
$\begingroup$ Pumping lemma? Take $xyz = 0^n1^n$ with $y=0$ and pump $y$? $\endgroup$– TurboNov 3, 2015 at 20:26