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 ?
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$.