# How to show that the language containing words which length are prime numbers isn't regular using pumping lemma?

I tried the following attempt :

It exists $p$ such that for all word $w\in L,|w|\ge p$. The lemma's conditions are satisfied. This is true for all $w$, therefore this is true in particular

• for $w=aaa\in L$ (But I don't know if I generalize enough, yet the first one which can generalize a formul for prime numbers is said to have found the one million dollar prize of the century...).
• for $w=a^p$, saying then that $p$ has a prime length.

Thanks to the pumping lemma we can write that

• $w=xyz$
• $|y|\ge 1$
• $|xy|\le p$
• $xy^iz\in L, \forall i\ge 0$

$|xy|\le p \Rightarrow |xy|$ can be or can't be of prime number length.

It's not sure that $|xy^iz|$ has a prime number length.

## Second attempt

Let's assume that $L$ is a regular language, then it satisfies the Puping Lemma. Let's take $w\in L$ such that $|w|$ is a Prime number.

We then take $w=xyz$ with $|xy|\le p$ and $|y|>$ (all of that to satisfy the Pumping Lemman).

Let's take $i=|xz|$ then $|xy^iz|=|xz|^2$ which isn't a prime number as far as it is the square of something. Therefore $|xy^iz|\not\in L$ for any $i$.

Yet, I don't feel like usin the pumping lemma here...

Can you help me formalize this proof ?

• If you take $i = |xz|$, what can you say about $|xy^iz|$? – Fabio Somenzi Apr 15 '17 at 19:17
• @FabioSomenzi would it be $|xy^iz|=|xz|^2$ ? Which isn't a prime number as far as it is the square of something ? – ThePassenger Apr 16 '17 at 10:08
• Not quite the square, because it depends on $|y|$, but still a multiple of $|xz|$, hence not prime. – Fabio Somenzi Apr 16 '17 at 13:49
• @FabioSomenzi thank you ! But do I use the pumping Lemma to prove that it's not regular ? – ThePassenger Apr 16 '17 at 16:59
• Yes, you do. The pumping lemma states that if the language is regular, there is a word you can "pump." However, you show that pumping this word would produce a word not in the language, contradicting the assumption that the language is regular. It's a textbook application of the pumping lemma. – Fabio Somenzi Apr 16 '17 at 21:45

Assume by contradiction that $L\in REG$.

Let $p \gt 0$ be the pumping constant of $L$.

Let $q \gt p$ be a prime number.

So $w = a \ ^ q \in L$ and its length is $q \gt p$, so by the pumping lemma we have $x,y,z \in \Sigma \ ^ *$ s.t $w = xyz$ , $|xy| \le p$ , $|y| \gt 0$and for each $i \in \Bbb N \cup \{0\}$ we have $x y \ ^ i z \in L$.

Denote by $n = |y|$ , so we have for $i = q+1,$ $xy\ ^ i z= a \ ^{q-n + n(q+1)} = a \ ^{(n+1)q}$ , so $|x y \ ^ {q+1} z| = (n+1)q$ and this is not a prime number because $n+1\gt 1$ divides it, so $x y \ ^ {q+1} z \notin L$ , contradiction.

Thus $L \notin REG$.

• Thank you for your answer, sorry for the delay, I'm not 24 hour a day on my computer. Yet, don't you miss a comma here : "so we have for $i = q+1$ , $xy\ ^ i z=...$" – ThePassenger Apr 18 '17 at 14:09
• @Marine1 yea, sorry for the misunderstanding. – user123 Apr 18 '17 at 19:20