Using pumping lemma to prove that $L:=\{a^{k^3} \mid k\geq 0\}$ is not regular

Question

I was practicing pumping lemma for my exams, but I got stuck on proving $L:=\left\{a^{k^3} \mid k\geq 0\right\}$ not regular so any idea is greatly appreciated !

After trials, I think I have reached a weak solution:

Suppose that

\begin{align} x= a^l \\ y= a^z \end{align}

so $$z = a^{{k^3} - L - Z}$$

now $$x(y^k)z = a^{(k^3) +kz -z} = a^{(k^3) +(k-1)z}$$

the contradiction is that $(k^3) +(k-1)z$ isn't an $n(k^3)$?

Answer 1

Pumping lemma proofs start with a few things:

• First, you need to assume the language is regular, and thus there is some number $p$ (the pumping number) such that for any string $s\in L$ of length longer than $p$ we can find $x$, $y$ and $z$ such as in the pumping lemma.
• You generally don't get to choose what these $x$, $y$ and $z$ are, since showing that a specific $x$, $y$ and $z$ make a string grow out of the language does not imply that the same holds for every choice of $x$, $y$ and $z$. The only things you get to choose are that $|y|>1$ and that $|xy|\leq p$.
• The correct first step is to take a suitable string $s\in L$ with length longer than $p$. Then we show up that regardless of how we choose $x$ and $y$ such that $xy$ is an (initial) substring of the first $p$ characters of $s$, we can pump $y$ to make $xy^kz$ fall outside of the language.

So let's apply this to your language $L=\left\{\mathtt a^{k^3}\mid k\geq 0\right\}$.

We assume that $L$ is regular, and thus let $p$ be the pumping length. Then the string $s=\mathtt a^{p^3}$ is a string longer than the pumping length, so there exist some $x$, $y$ and $z$ such that $s=xyz$, $|y|>0$ and $|xy|\leq p$, and such that for any $n\in \Bbb N$ we have $xy^nz\in L$ as well.

So let such $x$, $y$ and $z$ be given. Then \begin{align} x=\mathtt a^l\\ y=\mathtt a^m \end{align} for some $l$ and $m$ such that $l+m\leq p$. This means that $$z=\mathtt a^{p^3-l-m}$$ to make $xyz=\mathtt a^{p^3}$.

Now we have by assumption of $L$ being regular that $xy^nz=\mathtt a^{p^3+(n-1)\cdot m}$ is in $L$ for all $n\in\Bbb N$. This means that $p^3+(n-1)\cdot m=k^3$ for some $k$ for any $n\in\Bbb N$.

So we can get a contradiction if we can find an $n$ such that $p^3+(n-1)\cdot m$ is not a cube number. The easiest choice is probably $n=2$, which gives that $p^3+m=k^3$ for some $k$. Remember that $|xy|=l+m\leq p$ and $|y|=m>0$, thus in particular $1\leq m\leq p$.

Since $p^3+m>p^3$, we see that $k\geq p+1$. But: \begin{align} (p+1)^3&=p^3+3p^2+3p+1\\&>p^3+p\\&\geq p^3+m. \end{align} This is a contradiction, since it implies that $k^3>p^3+m$ for any possible candidate for $k$, while we needed $k^3=p^3+m$.

---

If you want to practice more, try to prove the following languages are not regular:

1. $L=\left\{\mathtt 0^{k^3-m}1^{m}\mid k\geq 0,\ \ 0\leq m\leq k^3\right\}$
2. $L=\left\{\mathtt 0^{k^3-m}1^{m}\mid k\geq 0,\ \ k\leq m\leq k^2\right\}$
3. $L=\left\{\mathtt 0^m1^{k^3}\mid m\geq 1,\ \ k\geq 0 \right\}$