2
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by fade2black, Evil, David Richerby, Hendrik Jan, J.-E. Pin Oct 9 '17 at 11:58

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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 $\endgroup$ – benguin Oct 8 '17 at 5:53
  • $\begingroup$ 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|$. $\endgroup$ – benguin Oct 8 '17 at 5:57
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do we know that p(1+s) isn't prime? $\endgroup$ – Adam Oct 8 '17 at 14:31
  • 1
    $\begingroup$ I'll let you figure that out. Note that $s \geq 1$ since $y \neq \emptyset$. $\endgroup$ – Yuval Filmus Oct 8 '17 at 15:35
  • 1
    $\begingroup$ p(1+s) is not prime because it is divisible by p. By definition prime numbers are only divisible by 1 or themselves. Since p != p(1+s) and p(1+s) is certainly divisible by p, we can conclude that p(1+s) is not prime. $\endgroup$ – kiwicomb123 Jun 18 at 2:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.