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?


  • 1
    $\begingroup$ 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. $\endgroup$
    – BrianO
    Feb 2 '16 at 1:11
  • $\begingroup$ @BrianO Hmm. Ok I was thinking that I couldn't do that. Do you have any suggestions on where to go then? :) $\endgroup$ Feb 2 '16 at 1:16
  • $\begingroup$ 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$. $\endgroup$
    – BrianO
    Feb 2 '16 at 1:25
  • $\begingroup$ Your attempt is actually close to an answer; see my answer on this related question. $\endgroup$
    – theyaoster
    Jun 18 '19 at 2:10

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.


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.