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.
UPDATE
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).