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?
Best Answer
No, this is not correct, you took one $w$, how do you know $A_1 \cup A_2=L$?
How ever, your idea is pretty close,here is a solution: