6
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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
    Commented Oct 8, 2017 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
    Commented Oct 8, 2017 at 5:57

1 Answer 1

Reset to default
6
$\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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ How do we know that p(1+s) isn't prime? $\endgroup$
    – Adam
    Commented Oct 8, 2017 at 14:31
  • 1
    $\begingroup$ I'll let you figure that out. Note that $s \geq 1$ since $y \neq \emptyset$. $\endgroup$
    – Yuval Filmus
    Commented Oct 8, 2017 at 15:35
  • 2
    $\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
    Commented Jun 18, 2019 at 2:12

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