9
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This even works for context-free languages. $\endgroup$ Commented Dec 4, 2013 at 17:05
9
$\begingroup$

Every regular language is accepted by some minimal DFA. For an infinite regular language $L$, let's call such a DFA $M_L$. Consider any state $q$ which can be visited more than once while processing some string in $L$. If $q$ can be visited more than once, it follows that it can be visited any number of times. Define $$L_1 = \{w \in L \mid q\text{ is visited an odd number of times}\}$$ and $$L_0 = \{w \in L \mid q\text{ is visited an even number of times}\}$$ This is a DFA, so there's only one path. Any string in $L$ is accepted by the DFA, and must visit the state some number of times (maybe zero). The state can be visited an unlimited number of times; therefore, we know that there are infinitely many strings in $L_1$ (since there are words that cause the state to be visited 1 time, 3 times, etc.) and that there are infinitely many strings in $L_0$ (since there are words that cause the state to be visited 0 times, 2 times, etc.). Any given string is either in $L_1$ or $L_0$, and cannot be in both, so $L_0 \cap L_1 = \emptyset$. However, any word in $L$ is guaranteed to be in one of these two sets, so $L_0 \cup L_1 = L$.

$\endgroup$
1
  • 2
    $\begingroup$ Still need to convince OP that the sublanguages are regular... $\endgroup$
    – vonbrand
    Commented Feb 9, 2020 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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