Proving that $L = \{0^k \mid \text{$k$ is composite}\}$ is not regular by pumping lemma

Question

Suppose $L = \{0^k \mid \text{$k$ is composite}\}$. Prove that this language is not regular.

What bugs me in this lemma is that when I choose a string in $L$ and try to consider all cases of dividing it into three parts so that in each case it violates lemma, I always find one case that does not violate it. A bit of help will be appreciated.

Thanks in advance.

---

My attempt:

1. Suppose that $L$ is regular.

2. Choosing string $x = 0^{2k}$ where $k$ is prime ($2k$ pumping constant)

3. We can divide $x$ into three parts $u, v, w$ such that: $$|uv| \le 2k \qquad |v| > 0\qquad uv^iw \in L \text{ for $i \ge 0$}$$

4. If $u$ and $w$ are empty, all conditions are met.

It is the same when I change $2$ for any other number. Maybe I'm choosing wrong.

Answer 1

You can’t assume that the pumping constant is even. If you want to start with a word of the form $0^{2k}$ for some $k$, that’s fine, but you can’t take $2k$ to be the pumping constant $p$; you can only assume that $2k\ge p$. But trying to use the pumping lemma directly to prove that $L$ is not regular is going to be a bit difficult. I would use the fact that the regular languages are closed under complementation, so if $L$ is regular, so is

$$L'=\{0^n:n\text{ is prime}\}\;.$$

Now apply the pumping lemma to $L'$. I’ve done it in the spoiler-protected text below, but I think that you can probably do it yourself without the help.

Let $p$ be the pumping length, and start with $x=0^n$ for some prime $n\ge p$. Decompose $x$ in the usual way as $uvw$, so that $|uv|\le p$, $|v|>0$, and $uv^kw\in L$ for $k\ge 0$. Let $a=|uw|$ and $m=|v|>0$; then for each $k\ge 0$ you have $|uv^kw|=a+km$. In other words, the lengths of the words $uv^kw$ form an arithmetic sequence with first term $a$ and constant difference $m$. You should have no trouble showing that this sequence must contain a composite number.