patternMinor
Partition an infinite regular language into 2 disjoint infinite regular languages
Viewed 0 times
infinitepartitionlanguagesintoregularlanguagedisjoint
Problem
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.
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.
Solution
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$.
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$.
Context
StackExchange Computer Science Q#18610, answer score: 9
Revisions (0)
No revisions yet.