Proving that $L := \{a^n\mid\exists k \geq 0\ n = k^3\}$ is not a regular language I'm having trouble using the pumping lemma to prove this language $L := \{a^n\mid\exists k \geq 0\ n = k^3\}$ is not regular.


*

*Assume $L$ is regular. Thus there is a DFA $M$ for it.

*Choose $m$ as the number of states in a DFA $M$.

*Choose $w = a^m$ such that $|w| \geq m$.

*Decompose $w = xyz$ such that $|xy| \leq 1$ and $|y| \geq 1$. Let $y = a^p$ where $p \geq 1$.

*Select an $i$ for $w_i = xy^iz$. Try $i = 0$.
Result is $a^{m-p}$.


Here's where I'm stuck.
 A: Hint. (1) State the pumping lemma for regular languages properly and be sure to understand it.
(2) Your step 5 is asking to find an $i$ such that $w_i = xy^iz \notin L$. You cannot just take a random $i$ and hope it will work.
A: Your third step isn’t quite right: $m$ need not be a perfect cube, so you can’t necessarily start with $a^m$. Start instead with $a^{k^3}$ for some positive integer $k$ big enough so that $k^3\ge m$.
Your fourth step also isn’t quite right, though I suspect that the error is just a typo: you mean that $|xy|\le m$. The pumping lemma then tells you that if $L$ is regular, $xy^iz\in L$ for each integer $i\ge 0$. Let $x=a^r$ and $y=a^s$, where $r+s\le m$ and $s\ge 1$. Then $z=a^{k^3-r-s}$, and
$$xy^iz=a^r(a^s)^ia^{k^3-r-s}=a^{k^3+(i-1)s}\;.$$
To get the desired contradiction, you must show that there is an integer $i\ge 0$ such that $a^{k^3+(i-1)s}$ is not a perfect cube.
Note that the sequence $\left\langle k^3+(i-1)s:i\ge 0\right\rangle$ is an arithmetic sequence with common difference $s$.


*

*Show that if $n\ge s$, then $(n+1)^3-n^3>s$.  

*Use this to show that if $i=s^2+1$, then $k^3+(i-1)s$ and $k^3+is$ cannot both be perfect cubes.  

*Conclude that there is at least one $j\ge 0$ such that $xy^jz\notin L$.

