# Proving L is regular or not using pumping lemma

So I'm trying to prove that the language $$L = \{1^n \mid n \text{ is composite}\}$$ is either regular or non-regular using the pumping lemma. I wanted to ask if I'm on the right track.

So I assume that $$L$$ is regular and let $$p = \text{pumping length}$$; Let $$s = 1^{2p}$$. $$s$$ is clearly in $$L$$, because $$2p$$ is composite. Since $$\mid s \mid > p$$, $$s = xyz$$ where for any $$i \geq 0, (x)(y^i)(z) \in L$$.

If we split $$x = \varepsilon$$, $$y = 1$$ and $$z = 2^{p-1}$$, then this satisfies the pumping lemma conditions. Now, because $$1$$ and $$2p-1$$ are coprime positive integers, the string $$xy^iz \notin L$$, because $$xy^iz$$ is the same as $$1^{i\cdot 1} \cdot 1^{2p-1}$$ or $$1^{i\cdot 1 + 2p - 1}$$.

And from a previously given theorem on number theory, for two coprime integers $$a,b$$, there exists a number $$n \geq 1$$, such that $$a + n \cdot b$$ is prime. Thus, $$L$$ cannot be regular.

I guess my real question is that when using the pumping lemma to prove non-regularity, is it sufficient enough to find one instance where the pumping lemma fails or do we need to prove that for all instances of $$x,y,z$$, the pumping lemma has to fail?

Thanks!

• You are given $x,y,z$, you can't just let $x=\varepsilon$ or whatever is convenient. At least, in the formulation of the pumping lemma that you're using. – BrianO Feb 2 '16 at 1:11
• @BrianO Hmm. Ok I was thinking that I couldn't do that. Do you have any suggestions on where to go then? :) – firesage123 Feb 2 '16 at 1:16
• Use a strong form of the pumping lemma. Briefly, in a regular language $L$, any sufficiently long substring of a string in $L$ has a substring that can be pumped. To spell that out: If $L$ is regular, there is a $p\in\Bbb N$ s.t. for any $w\in L$, if there are $s,u,y$ with $w=sut$ and $|u|\ge p$, then for some $x,y,z$, $u = xyz$ and for all $i\ge 0$, $sxy^izt \in L$. // But on further reflection, perhaps it doesn't matter after all: the alphabet has only one symbol, so $1^a1^b = 1^b1^a$. – BrianO Feb 2 '16 at 1:25

Suppose that $$L$$ is regular. Then the language $$P = 1^+ - L$$ is also regular. Observe that $$P = \{1^p \mid p \text{ is prime } \}$$. Since $$P$$ is infinite, the pumping lemma can be applied: there exists $$N$$ such that every word $$w$$ of $$P$$ of length at least $$N$$ can be written as $$w = xyz$$, where $$x, y, z \in 1^*$$, $$0 < |y| \leqslant N$$ and $$xy^*z \subseteq P$$.
Let us apply this result to $$w= 1^p$$, where $$p$$ is a prime number $$> N+1$$. Let $$n = |xz|$$. Since $$|w| = |xyz| > N+1$$ and $$|y| \leqslant N$$, one has $$n \geqslant 2$$. Since $$xy^*z \subseteq P$$, one has $$xy^nz \in P$$. However $$|xy^nz| = |xz| + |y^n| = n + n|y| = n(1+|y|).$$ Since $$n(1+|y|)$$ is a composite number, one gets $$xy^nz \notin P$$, a contradiction.