Decomposing an infinite regular language

Question

Let $L$ be an infinite regular language. Prove that $L$ can be split up into $L_1, L_2$, so that $L_1 \cup L_2 = L$ and $L_1 \cap L_2 = \emptyset$

Can you give me some directions to do it? Thanks in advance.

Answer 1

Hint: Regular languages are closed under union, intersection, and complement. (see http://en.wikipedia.org/wiki/Regular_language#Closure_properties). So if your language $L$ contains a string $s$, build a regular language that recognizes just $s$ and also a regular language that recognizes $L \cap s^c$, i.e. all strings in $L$ except $s$.

Answer 2

Given the hypothesis that $L$ is infinite, I suspect that $L_1$ and $L_2$ are supposed to be infinite as well. You can actually use the pumping lemma to help you here. Let $p$ be the pumping length for $L$, and let $w\in L$ with $|w|\ge p$. Use the pumping lemma to decompose $w$ as $w=xyz$, where $|y|\ge 1$, and $xy^kz\in L$ for each $k\ge 0$, and let $L_1=\left\{xy^{2k}z:k\ge 0\right\}$. Then show that $L_1$ and $L_2=L\setminus L_1$ are regular and infinite; you’ll want the closure properties of regular languages to get regularity $L_2$.