# I can construct DFA for $a^{3n+1}$ but pumping lemma says it is not regular

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

• 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. Jun 3, 2018 at 12:38
• 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? Jun 3, 2018 at 13:06
• 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. Jun 3, 2018 at 13:43

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.
• But with your decomposition $\mid xy \mid \nleq p$ Jun 3, 2018 at 14:56
• @tokenizer it is corrected. there exists a $p$ such that ...