2
$\begingroup$

Prove that the language that consists of cube numbers as strings is not regular.

I wanted to use pumping lemma but couldn't $$0, 1, 8, 27, 64, 125, 216, \dots$$

$\endgroup$
2
  • $\begingroup$ Hm. { iⁱⁱⁱ, iiⁱⁱⁱ, iiiⁱⁱⁱ, iiiiⁱⁱⁱ, … } $\endgroup$
    – greybeard
    Apr 4 at 16:15
  • $\begingroup$ Please don't roll back edits that others make to your question. See cs.stackexchange.com/help/editing. $\endgroup$
    – D.W.
    Apr 5 at 4:51
1
$\begingroup$

Denote your language by $L$. Suppose that the pumping length is $p$. Consider $$ N = (10^{p+1} + 1)^3 = 10^{3p+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1, $$ whose decimal encoding is $$ w = 1 0^p 3 0^p 3 0^p 1 \in L. $$ According to the pumping lemma, we can write $w = xyz$ so that $|xy| \leq p$, $y \neq \epsilon$, and $xz \in L$. Since $|xy| \leq p$, the part $xy$ lies within the prefix $10^{p-1}$. If $y$ contains $1$ then $xz$ has a leading zero, which is impossible (if you allow leading zeroes, consider $L \cap (1+9)(0+9)^*$ instead), so $y$ consists only of zeroes. Hence $$ xz = 10^q 30^p 30^p 1, $$ for some $q < p$, which encodes the number $$ n = 10^{2p+q+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1. $$ If $xz \in L$ then $n$ is a cube. Since $n$ ends with $1$, necessarily $n = 10m + 1$ (you can check this directly by considering $0^3,1^3,\dots,9^3$), and so $$ 10^{2p+q+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1 = 1000 m^3 + 300 m^2 + 30m + 1, $$ which implies that $$ (10^{p+q+2} + 3 \cdot 10^{p+1} + 3) 10^p = (100 m^2 + 30 m + 3) m. $$ Clearly $100m^2 + 30m + 3$ is divisible by neither $2$ nor $5$ (its units digit is $3$), and so $10^p$ must divide $m$. In particular, $m \geq m_0 := 10^p$. However, this is impossible, since $N = (10m_0 + 1)^3$, and $n < N$.

$\endgroup$
2
  • $\begingroup$ Just imagine 10000000000000000000000000001^3, with the amount of zeros exceeding the pumping length. $\endgroup$ Apr 4 at 18:28
  • $\begingroup$ @user15550465 The decimal encoding of a number is its encoding in base 10. For example, the decimal encoding of 81 is 81 (its hexadecimal encoding, in contrast, is 51). Your language consists of all decimal encodings of cubes (with or without leading zeroes — you haven't made that clear). $\endgroup$ Apr 4 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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