I have this language: $$ L = { \{\ a^{i^{2}} : i \in N \ \cup \{0\} \ \}} $$

I need to prove that the language is not regular by using pumping lemma. I assume that the language is regular so I choose suitable word with which I will be trying to prove that it's not regular language.

The word that is suitable should be $w = a^{p^{2}}$ then I can decompose that word to $xyz$ parts $$|xy| \leq p \ \land |y| \ge 1$$

The decomposition is: $$x = a^{l}\land l\ge0\\y= a^{k}\land k\ge1\\z=a^ma^{p^{2}-p}\land m\ge0\\l+k+m=p\ \land l+k\leq p $$

Now I will pump the $y$ part in $xy^{i}z$ so the word won't be in the language anymore and that means that the language was not regular.

The problem is I have absolutely no idea which $i$ should I choose to break the pumping property and show that the language was not regular. Could anyone explain me for what I should be searching in order "break" pumping property and what $i$ to choose?


marked as duplicate by J.-E. Pin, Claude Leibovici, fonfonx, Fabio Somenzi, José Carlos Santos Jan 5 '18 at 18:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


You have

$$xy^iz=a^\ell a^{ik}a^{p^2-k-\ell}=a^{p^2+(i-1)k}\;,$$

so you want to choose $i$ so that $p^2+(i-1)k$ is not a perfect square. There are several ways to do this, but the simplest is to let $i=0$ and prove that $p^2-k$ is not a perfect square; use the fact that $1\le k\le p$. HINT: Compare $p^2$ and $(p-1)^2$.


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