The language L = { $a^n $ such that $n = b^2$ for some integer b } is not regular. Prove it using Pumping Lemma for Regular Languages.

Question

This is the Pumping Lemma for regular languages I refer:

For all regular languages $L$, there exists some $k \in \mathbb{N}$ such that for all $xyz \in L$ with $|y| \ge k$, there exist $uvw = y$ with $|v|> 0$, such that for all $i \ge 0, xuv^iwz \in L$.

---

Let $L = \left \{ a^n \mid n = b^2 \mbox{ for some integer } b \right \}$. Using Pumping Lemma for Regular Languages, prove that $L$ is not regular.

1. Proof is by contradiction using the Pumping Lemma for Regular Languages. Assume $F$ regular, so the PL holds for L. Let $k$ be as given by the PL.

2. Choose $x,y,z$ as:
   $\begin{array}{rcl} x & = & \epsilon \\ y & = & a^k \\ z & = & a^{k^2-k}\end{array}$
   Now, $xyz = a^{k^2} \in L$, and $\left | y \right | \ge k$ as required.

3. Let $u,v,w$ be as given by the PL, so that:
   $\begin{array}{rcl}uvw & = & y \\ \left |v \right | & > & 0 \\ \forall i, xuv^iwz & \in & L \end{array}$

4. Choose $i = 2$. The string $xuv^2wz$ has one extra copy of $v$. We know that $0 < |v| \le k$, so $xuv^2wz = a^p$, where $k^2 < p \le k^2+k$. But, then $p$ falls stricty between $k^2$ and the next larger square, $(k+1)^2 = k^2+2k+1$. So, $p$ cannot be the square of an integer, and $xuv^2wz \notin L$

5. By contradiction, $L$ is not regular. $\Box$

---

There are some parts I don't understand: I understand that we have rewritten $a^{k^2}$ doing the following:
$\begin{array}{lcl}a^ka^{k^2}a^{-k} & = & a^{k-k}a^{k^2} \\ & = & a^0a^{k^2} \\ & = & a^{k^2} \end{array}$
in order to pump the content of $y$.

But, I have some difficulties in the point 4: It is clear that $0 < |v| \le k$, i.e. we don't know what $|v|$ is exactly; it can be at least $1$, but, it can be equal to $k$, i.e. if $|v| = k$ then $|u| = |w| = 0$. But, the following it is not clear:

so $xuv^2wz = a^p$, where $k^2 < p \le k^2+k$. But, then $p$ falls stricty between $k^2$ and the next larger square, $(k+1)^2 = k^2+2k+1$.

In addition:

if

$\begin{array}{rcl}b=0 & : & n = 0^2 = 0 \\ b=1 & : & n = 1^2 = 1 \\ b =2 &: & n = 2^2 = 4 \\ b = 3 & : & n= 3^2 = 9 \\ \vdots \end{array}$

so, is it right to consider the language as $L = \left \{ \epsilon, a, aaaa, aaaaaaaaa, a_1 \cdots a_{16}, \ldots \right \}$ ?

---

If possible can you explain me in a more practical way using a string of the language, for example using $a_1 \cdots a_9$? And however, any help to understand is appreciated! Many thanks! :)

Answer 1

Using the pumping lemma is a complicated way to prove that your language is not regular, but since you insist...

It follows from your step 3, that for all $i$, the word $h_i = xuv^iwz$ is in $L$. Setting $xuwz = a^r$ and $v = a^n$, one gets $a^r(a^n)^* \subseteq L$. Thus if you order the words of $L$ by increasing length, the length gap between two consecutive words of length $\geqslant r$ is at most $n$. This is a contradiction, since the gap between $(r+n+1)^2$ and $(r+n)^2$ is $> n$.