# Show that a language consisting of strings of a prime number of 1s is irregular using pumping lemma [duplicate]

Question:

L is a language defined as $\ L = \{1^l | l\in primes\}$ (strings of 1s having a prime length). Show that this is not a regular language ($\ L \notin REG$). You may either use the theory of closure or the pumping lemma to prove this.

My try:

So far I have tried to take a word $\ w | w=1^p$ ($\ p$ being the pumping value), but in this case I don't know how to prove that every decomposition of the form $\ w=xy^i z$ is invalid. When $\ |y|=p$ (and therefore $\ x=z= \epsilon$) the lemma is clearly untrue, because when $\ i = 2$, $\ |w'| = 2p$ which is not prime. But in the case that $\ y<p$, and $\ x \neq \epsilon$ and/or $\ z \neq \epsilon$, I don't see a way to prove that $\ w' = x y² z$ is not prime.

• Just a few notes: notice the pumping lemma says that $xy^iz$ needs to be in $L$ for all $i$, thus, for your proof by contradiction, you just need to show $xy^iz$ is not in $L$ for some $i$ (and this value of $i$ that will need in your proof won't necessarily always be 2). Secondly, the pumping lemma states that the lemma holds for all strings of at least length $p$ that are in $L$. Notice that $1^p$ may not necessarily be in $L$ because we don't know that $p$ (the pumping value) is actually prime – benguin Oct 8 '17 at 5:53
• An example of a string in the language that you could use the pumping lemma on would be $1^q$ where $q$ is the smallest prime that's at least as big as $p$. (I can't promise this is the best choice for solving the problem though). As for picking $i$, it may be that you need to express it as some function of $|x|, |y|,$ and $|z|$. – benguin Oct 8 '17 at 5:57

Your attempt doesn't work, since you need the word you pick to belong to the language. Therefore I suggest picking $w = 1^p$, where $p$ is a prime which is larger than the pumping constant. The pumping lemma shows that there is a decomposition $w=xyz$, where $y \neq \epsilon$, such that $xy^iz \in L$ for all $i \geq 0$. Let $x=1^r$, $y=1^s$, and $z=1^t$, so that $r+s+t=p$. Then $xy^iz = 1^r 1^{si} 1^t = 1^{r+si+t} = 1^{p+(i-1)s}$. Thus, $p+(i-1)s$ has to be prime for all $i \geq 0$. However, when $i = p+1$, we get $p+(i-1)s = p+ps = p(1+s)$, which isn't prime.
• I'll let you figure that out. Note that $s \geq 1$ since $y \neq \emptyset$. – Yuval Filmus Oct 8 '17 at 15:35