1

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.

Christian E. Ramirez
  • 3,377
RandomGuyOnMath
  • 11
  • The emphasize one small part of David's answer below: When using the Pumping Lemma, you should always start with something like "Assume the language is regular, and let $m$ be the pumping length." This is the length such that, if any string $w$ is at least this long, then all the rest of the pumping lemma follows. You will then want to (strategically) pick some string which you can prove has length at least $m$, and from which you derive a contradiction. – Addem Mar 22 '23 at 01:19
  • Using the pumping lemma to show that $L$ is regular is actually a very bad idea, since an elementary proof suffices. Since $L$ is regular and infinite, it contains a language of the form $a^k(a^n)^*$ with $k < n$. This means that the gaps between the lengths of the words of $L$ is at most $n$. But since $(n+1)^2 - n^2 = 2n + 1$, $L$ does not satisfy this condition and hence is not regular. – J.-E. Pin Mar 25 '23 at 11:17

1 Answers1

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.

David
  • 82,662
  • So we can not choose our own xyz and have to come up with a contradiction that works for every xyz. I've seen some proofs where they chose their own xyz, does it depend on the context? – RandomGuyOnMath Mar 22 '23 at 14:45
  • If it's proving a language not regular by contradiction, I can't see how this would ever be possible, so those proofs would be wrong. (But maybe I missed something.) The vital thing is to make sure you are clear on which parts of the theorem are "there exists" and which are "for all". However there is the more advanced version of PL which applies to all words $w_1w_2w_3$ in $L$ with $|w_2|\ge m$. So you can choose $w_1,w_2,w_3$. It then goes on to say "there exist $x,y,z$ such that $w_2=xyz$ and (etc). So you cannot choose $x,y,z$ but must consider all possibilities. – David Mar 23 '23 at 12:42