[Solved]: Partition an infinite regular language into 2 disjoint infinite regular languages

Problem Detail: 

Given any infinite regular language $L$, how can I prove that $L$ can be partitioned into 2 disjoint infinite regular languages $L_1, L_2$? That is: $L_1 \cup L_2 = L$, $L_1 \cap L_2 = \varnothing$, and $L_1$ and $L_2$ are both both infinite and regular.

So far, I thought of:

1. using the pumping lemma such that $$ \begin{gather} L_1 &= \{ xy^nz \mid \text{\(n\) is even} \} \\ L_2 &= \{ xy^mz \mid \text{\(m\) is odd} \} \\ \end{gather} $$ but couldn't prove that they are dijoint or covering $L$ completely.

2. Using the regular language partitions $\Sigma^*$ into dijoint equivalence classes, but I haven't figured out how to determine if an equivalence class is regular or infinite.

Asked By : Tom

Answered By : Yuval Filmus

Let $S = \{ |w| : w \in L \}$. Parikh's theorem shows that $S$ is an eventually periodic set. Let the eventual period be $\ell$. Since $L$ is infinite, there is some offset $a$ such that $a + k\ell \in S$ for all $k \geq 0$. Thus the language $L_1 = \{ w \in L : |w| \equiv a \pmod{2\ell} \}$ is infinite (it contains all words of length $a + 2k\ell$ for some $k \geq 0$), and the language $L_2 = L \setminus L_1$ is also infinite (it contains all words of length $a + (2k+1)\ell$ for some $k \geq 0$, as well as possibly other words). I'll let you show that $L_1,L_2$ are both regular.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18610