Proving that $L := \{a^n\mid\exists k \geq 0\ n = k^3\}$ is not a regular language

Question

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.

1. Assume $L$ is regular. Thus there is a DFA $M$ for it.
2. Choose $m$ as the number of states in a DFA $M$.
3. Choose $w = a^m$ such that $|w| \geq m$.
4. Decompose $w = xyz$ such that $|xy| \leq 1$ and $|y| \geq 1$. Let $y = a^p$ where $p \geq 1$.
5. Select an $i$ for $w_i = xy^iz$. Try $i = 0$. Result is $a^{m-p}$.

Here's where I'm stuck.

Answer 1

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.

Answer 2

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$.