Recently I stumbled across this language $L=\{a^{n}a^{{(n + 1)}^2-n^2} \in \Sigma^* \mid n\geq 0\}$ that I can rewrite as $a^{3n + 1}$.

So I applied the pumping lemma to see if it is non regular, and I get:

  • given a pumping length p I should have a string $z\in L$ such that $\mid z \mid \ge p$
  • I choose $z=a^pa^pa^pa$ such that $z\in L$ and $\mid z \mid = (3p + 1)\ge p$
  • now I can slipt the string in 3 parts, $z=uvw$ with $u=a^{p-1}, v=a,w=a^{2p}a$ and it satisfies the two following conditions of the lemma $\mid uv \mid \leq p$ and $\mid v \mid > 0$
  • then given $z = uv^iw$, if I pump $v$ I see that $z \notin L$ because if for example I choose $i=2$ than $\mid z \mid = (p-1)+i+2p+1=3p+2 \geq 3p+1$

So $z \notin L$ and it means that $L$ is not regular, but I noticed that I can construct a DFA that accepts this language:


So now I'm really confused. Probably I'm applying the pumping lemma in the wrong way but I don't understand where.


Now, thanks to all of you, I think I understood my mistake. So to prove that a language is not regular I have to show that every decomposition fails to satisfy the pumping condition for some pumping number $i$. But in this case there is a decomposition that satisfies the pumping condition so I can't prove that the language is regular (but we know it is regular because we can construct a DFA that accepts it).

  • $\begingroup$ This is a classic mixup. The pumping lemma states that there exists a decomposition of long enough words $w\in L$ to $w=xyz$ such that $xy^iz\in L$ for all $i$. In your case, choosing $y=aaa$ works, the pumping lemma does not state that every decomposition works. $\endgroup$ – Ariel Jun 3 '18 at 12:38
  • $\begingroup$ Ok, but now I'm confused on how to decompose the string. If I want to prove that a language is not regular, shoudn't I choose a decomposition that belongs to the language and pump it with an arbitrary $i$ such that the pumped string doesn't belong anymore to the language? $\endgroup$ – tokenizer Jun 3 '18 at 13:06
  • $\begingroup$ No you have to show that every decomposition fails to satisfy the the pumping condition for some pumping number $i$ if you want to show that a language is not regular. $\endgroup$ – ttnick Jun 3 '18 at 13:43

You should notice that if the conditions hold, the language can be regular (necessary, but not sufficient). However, you proved the third condition is not held in your case, hence it is not regular which this is not true. Therefore, your proof is not correct.

On the other hand, if we suppose $x = a$ and $y = a^{3}$ and $z = 3n-4$ we can say $xy^nz$ is in $L$ for all $n\geq1$ ($p = 4$). Hence, we can't proof $L$ is not regular by pumping lemma.

  • $\begingroup$ This is not true for every language. The pumping lemma is only a necessary condition for regularity. There are languages where all conditions are satisfied but are not regular. $\endgroup$ – ttnick Jun 3 '18 at 13:45
  • $\begingroup$ @PHPNick Yes. I've corrected it to "can be regular". $\endgroup$ – OmG Jun 3 '18 at 13:46
  • 1
    $\begingroup$ But with your decomposition $\mid xy \mid \nleq p$ $\endgroup$ – tokenizer Jun 3 '18 at 14:56
  • $\begingroup$ @tokenizer it is corrected. there exists a $p$ such that ... $\endgroup$ – OmG Jun 3 '18 at 15:05

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.