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$?

How ever, your idea is pretty close,here is a solution:

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$.

  • $\begingroup$ 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$. $\endgroup$ – TheNotMe Nov 30 '13 at 9:06
  • $\begingroup$ Suppose $L=a^*$, $w=aaaaaaaa$,$x=a$,$y=aaaa$,z=$aa$. Now $A_1 \cup A_2$ just gives $a^{4k+3}$. $\endgroup$ – hhsaffar Nov 30 '13 at 9:09
  • $\begingroup$ @TheNotMe Suppose $L=a^*$, $w=aaaaaaaa$,$x=a$,$y=aaaa$,z=$aa$. Now $A_1 \cup A_2$ just gives $a^{4k+3}$. $\endgroup$ – hhsaffar Nov 30 '13 at 9:11
  • $\begingroup$ I see.., thanks for the heads up $\endgroup$ – TheNotMe Nov 30 '13 at 9:11
  • $\begingroup$ @TheNotMe However, your idea is pretty close, I updated my answer with a solution. $\endgroup$ – hhsaffar Nov 30 '13 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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