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
    Commented Apr 4, 2021 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.
    Commented Apr 5, 2021 at 4:51

1 Answer 1

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$ Commented Apr 4, 2021 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$ Commented Apr 4, 2021 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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