Using pumping lemma to prove that $L:=\{a^{k^3} \mid k\geq 0\}$ is not regular 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)$?
 A: 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:


*

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

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

*$L=\left\{\mathtt 0^m1^{k^3}\mid m\geq 1,\ \ k\geq 0 \right\}$
