# 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. – Ariel Jun 3 '18 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? – tokenizer Jun 3 '18 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. – ttnick Jun 3 '18 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$ – tokenizer Jun 3 '18 at 14:56
• @tokenizer it is corrected. there exists a $p$ such that ... – OmG Jun 3 '18 at 15:05