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 ?

  • 1
    $\begingroup$ If you take $i = |xz|$, what can you say about $|xy^iz|$? $\endgroup$ – Fabio Somenzi Apr 15 '17 at 19:17
  • $\begingroup$ @FabioSomenzi would it be $|xy^iz|=|xz|^2$ ? Which isn't a prime number as far as it is the square of something ? $\endgroup$ – ThePassenger Apr 16 '17 at 10:08
  • $\begingroup$ Not quite the square, because it depends on $|y|$, but still a multiple of $|xz|$, hence not prime. $\endgroup$ – Fabio Somenzi Apr 16 '17 at 13:49
  • $\begingroup$ @FabioSomenzi thank you ! But do I use the pumping Lemma to prove that it's not regular ? $\endgroup$ – ThePassenger Apr 16 '17 at 16:59
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ 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=...$" $\endgroup$ – ThePassenger Apr 18 '17 at 14:09
  • $\begingroup$ @Marine1 yea, sorry for the misunderstanding. $\endgroup$ – user123 Apr 18 '17 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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