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