0
$\begingroup$

This question already has an answer here:

I'm struggling to understand this question using pumping lemma to prove a language is not regular. Any help would be appreciated.

Prove using the Pumping Lemma that the following language is not regular.

{0^n^3 |n ≥ 0 is an integer}

From my understanding a language isn't regular if the power is linear. But I just cant get my head around using the Pumping Lemma to prove this even after reading other examples of Pumping Lemma.

I think most expressions require you to split them into seperate parts, but I just dont understand how this is possible for this expression.


$\endgroup$

marked as duplicate by David Richerby, Raphael Dec 12 '17 at 15:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3
$\begingroup$

Your language could be rewritten more clearly as:

$\{ a^m \mid m \text{ is a perfect cube} \}$

Now you'd have to find a word from this language, longer than the pumping length $p$, that can not be pumped. We choose as a candidate: $a^{p^3}$. We name our three substrings $x, y, z$, which must be of the form:
$x = a^i$
$y = a^j$
$z = a^{(p^3 - i - j)}$

The pumping lemma restricts $j$ to be greater than $0$ and $i + j \le p$. It's sufficient to show that there exists at least one integer $k \ge 0$, such that $xy^kz$ is not a valid word in the language. Because of our separation, we need to find a $k$ such that $p^3 + (k - 1)j$ is not a perfect cube.
Let's say $k = 2$, which gives us $p^3 + j$, strictly increasing with respect to $j$, having a maximum value of $p^3 + p$.
We also know that the smallest perfect cube larger than $p^3$ is $(p + 1)^3 = p^3 + 3p^2 + 3p + 1$.

Because $p^3 \lt (p^3 + p) \lt (p+1)^3, \forall p \gt 0$, our pumped string's length can't be a perfect cube (because it's strictly between two consecutive perfect cubes).

So the language contains at least one word longer than the pumping length that can't be pumped, which means the language isn't regular.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.