Using pumping lemma show that language $L = \{a^{n^2} | n≥ 0\}$ is not regular.

Question

Using pumping lemma show that language $L = \{a^{n^2} | n≥ 0\}$ is not regular.

Is this approach correct?

Let's assume that $L$ is regular so then the pumping lemma applies.

Let $w = a^{n^2} ∈ L$.

We can split $w$ into $w = xyz$ such that $|y| > 0 ,\ |xy| ≤ z$,$\ \forall i ≥ 0: xy^iz ∈ L$

$$|w|=n^2 ≥ n$$

Let $x,y,z$ be:

$$\begin{split} x& = λ\\ y &= a^k, k > 0, k ≤ n\\ z &= a^{n^2-k}\\ \end{split}$$

If $i = 2$,$\ w^* = xyyz ∈ L$, $\ w^*=a^{n^2+k}$, because $1≤k≤n$ then:

$$n^2<n^2+k<(n+1)^2 \implies n^2<|xy^2z|<(n+1)^2 \implies xy^2z ∉ L$$

That is a contradiction with the pumping lemma so $L$ is not a regular language.

Answer 1

You need to be more careful with the logic. The Pumping Lemma says that if $L$ is regular then

• there exists $m>0$ such that
• for all $w\in L$, if $w$ has length $m$ or more, then
• there exist $x,y,z\in \Sigma^*$ such that
• $y$ is not empty, and
• for all $n\ge0$, $xy^nz\in L$

(six quantifiers!!!). So, supposing that $L$ is regular, you need do something like this.

• Let $m$ have the property stated.
• Choose a suitable $w$, say $w=a^{n^2}$ with $n^2\ge m$.
• Let $x,y,z$ be words with the stated properties. This is the main problem in your proof - the Pumping Lemma says that such words exist, but does not say what they are, so you cannot assume $x=\lambda$, and in particular, you cannot assume that $y=a^k$ with $k\le n$. It is clear that $y$ (being a subword of $w$) is a string of $a$s, but all you know for sure is that its length is greater than zero and at most $n^2$.
• In particular, taking $i=2$ does not work as this gives $$|xy^2z|=n^2+k\ ,$$ and you do not know for sure that this is less than $(n+1)^2$.
• However, we do know that $xy^iz$ is in $L$ for all $i$, which means that $n^2+(i-1)k$ is a square for all $i$, and we have to get a contradiction out of this.

This is a little tricky. One way is to observe that the gaps between squares increase, so soon or later, the value of $n^2+(i-1)k$ must "fall into a gap" and not be a square.

Another way is to play around a little bit and find that if $i=n^4k+1$ then $$(n^2k)^2<|xy^iz|<(n^2k+1)^2\ .$$

The best way of all is to use the more advanced version of the Pumping Lemma, see here for example.