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:
- 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.
- 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 + kell in S$ for all $k geq 0$. Thus the language $L_1 = { w in L : |w| equiv a pmod{2ell} }$ is infinite (it contains all words of length $a + 2kell$ 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
