# Possible solution for Sipser 1.63

Sipser's question 1.63:

Let A be an infinite regular language. Prove that A can be split into two infinite disjoint regular subsets.

Is my solution correct?

Since $A$ is infinite and regular, then the pumping lemma holds. We have a pumping length $p \geq 0$ for this language. We take one word $w$ in $A$ such that $|w| \geq p$, and according to the pumping lemma we split it into $w = xyz$ as in the lemma.

We then define the two languages like this:

$A_1$ contains all the strings $xy^{2i}z, i\geq 0$

$A_2$ contains all the strings $xy^{2i + 1}z, i \geq 0$

That means that $A_1$ contains all the strings that go an even number of times in that cycle, and $A_2$ all the strings that go an odd number of times in that cycle.

We note that we have also covered the words that are not related to the word we split, since $0$ is even.

Is this a correct approach?

No, this is not correct, you took one $w$, how do you know $A_1 \cup A_2=L$?
Consider $A_1=\{xy^{2k}z\}$ and $A_2=L-A_1$, Clearly $A_1$ is infinite, also $A_2$ is infinite because $\{xy^{2k+1}z\}\subseteq A_2$.
• because $xy^nz, n\geq 0$are all in L, and the ones that are not related to it are also in $A_1$ because $0$ is even and $xz$ are all in $L$. – TheNotMe Nov 30 '13 at 9:06
• Suppose $L=a^*$, $w=aaaaaaaa$,$x=a$,$y=aaaa$,z=$aa$. Now $A_1 \cup A_2$ just gives $a^{4k+3}$. – hhsaffar Nov 30 '13 at 9:09
• @TheNotMe Suppose $L=a^*$, $w=aaaaaaaa$,$x=a$,$y=aaaa$,z=$aa$. Now $A_1 \cup A_2$ just gives $a^{4k+3}$. – hhsaffar Nov 30 '13 at 9:11