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?

  • 4
    $\begingroup$ Consider $L_i=\{w\in\{a,b\}^*\ |\ |w|_a-|w|_b\le i\}$. $\endgroup$ – Klaus Draeger Nov 3 '15 at 20:54

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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