1
$\begingroup$

I need to prove that the following language is not regular by showing there are infinite pairwise distinct equivalence classes: $$ L = \{a^{n^3} \mid n \geq 1\} \subseteq \{a\}^* $$

Looking at a few examples, I intuitively noticed that for each $i \geq 1$ there is an equivalence class $[a^{i^3}] \neq [a^{j^3}]$ for $i \neq j$ because the number of $a$'s we need to add increases exponentially with $i/j$. Thus for every $i$ we can add a suffix of $a$'s to reach the next higher power $(i+1)^3$ but the length of that suffix is different for every other power, so that each equivalence class only actually contains the representative itself.

Example: $$ \begin{align*} &n = 1 \implies a \\ &n = 2 \implies a^8 \\ &n = 3 \implies a^{27} \\ \vdots \end{align*} $$ Then $$ \begin{align*} & [a] = \{x \in \{a\}^* \mid a \; R_L \; x\} = a \\ & [a^8] = \{x \in \{a\}^* \mid a^8 \; R_L \; x\} = a^8 \\ \vdots \end{align*} $$ Consider $[a]$. For $z = a^7$ we get $az = aa^7 = a^8 \in L$, but starting from $i \geq 2$, we have that $a^{i^3}z \notin L$.

How can I write this down in a more formal/rigorous way?

$\endgroup$
2
  • 2
    $\begingroup$ For $i\neq j$, let $k=\min(i,j)$. Then $z=a^{3k^2+3k+1}$ distinguishes $x=a^{i^3}$ and $y=a^{j^{3}}$. In fact, assume that $k=i$. Then $xz=a^{(i+1)^3}\in L$, while $yz=a^{j^3+3i^2+3i+1}\notin L$. The latter assertion is because $j^3<j^3+3i^2+3i+1<j^3+3j^2+3j+1=(j+1)^3$. Since $j^3+3i^2+3i+1$ is strictly between two consecutive cubes, it cannot itself be a cube. $\endgroup$
    – plop
    May 13, 2021 at 20:55
  • $\begingroup$ Thanks @plop. Would have definitely given you a green mark :) $\endgroup$ May 13, 2021 at 21:59

1 Answer 1

2
$\begingroup$

More generally, you can use Myhill–Nerode to prove the following characterization:

For $A \subseteq \mathbb{N}$, let $L(A) = \{ a^n : n \in A \}$.

The language $L(A)$ is regular iff $A$ is eventually periodic.

In particular, if $A$ is an infinite set with density zero then $L(A)$ is not regular. Here density zero means:

$$ \lim_{n\to\infty} \frac{|A \cap \{0,\ldots,n-1\}|}{n} = 0. $$

This shows that $\{a^{n^k} : n \in \mathbb{N}\}$ is not regular for any $k \geq 2$.


Let us prove the claimed characterization. If $A$ is periodic, say with period $m$, then $L(A)$ is clearly regular: it is accepted by a circular DFA with $m$ states. If $A$ is eventually periodic then there is a periodic $B$ such that $L(A),L(B)$ differ in finitely many words, and so standard closure operations show that $L(A)$ is regular.

Now suppose that $L(A)$ is regular. The equivalent class of $a^m$ is the set $E_m = \{ k \in \mathbb{N} : m+k \in A \}$. Since there are finitely many equivalence classes, there exist $m < p$ such that $E_m = E_p$, that is, for all $k \in \mathbb{N}$, $m + k \in A$ iff $p + k \in A$. In other words, for all $\ell \geq m$, $\ell \in A$ iff $\ell + (p-m) \in A$. Hence $A$ is eventually periodic (with period $p-m$).

$\endgroup$

Your Answer

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

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