# Proving that L is not regular by showing that $\equiv_L$ has infinite index

Proving that L is not regular by showing that $$\equiv_L$$ has infinite index.
$$\Sigma$$ = {a}, L = {$$a^{3^n} : n \geq$$ 0}
My ideas:
theorem of Myhill-Nerode: L $$\in$$REG $$\Leftrightarrow$$ $$\equiv_L$$ has finite index
We show: $$\equiv_L$$ has infinte equivalence classes.
$$a^{3^i}$$ $$\not\equiv$$ $$a^{3^{i+k}}$$, $$k>0$$
-> equivalence classes: [a], [aaa], [$$a^3$$]...
Every $$a^{3^i}$$ is a different equivalence class. Therefore $$\equiv_L$$ has an infinite amount of equivalence classes $$\rightarrow$$ L is not regular. qed.

How to show that the classes are different?

• I dont know how you say, that the equivalence classes are different. So how to show that?
– joee
Nov 12, 2018 at 11:20
• Okay, that's a fair question. Hint: you're trying to show inequality of sets.
– Raphael
Nov 12, 2018 at 13:27
• Be careful, there are many more equivalence classes, you only show the ones that make up your language. That is enough, as if those are infinite in number, the index of the relation is also infinite. But need to state it for completeness. Feb 15, 2020 at 11:55

Let me prove a stronger claim: every two words over $$\{a\}$$ are inequivalent with respect to your language. What this means is that for every $$i \neq j$$, there is a word $$w \in a^*$$ such that either $$a^i w \in L$$ and $$a^j w \notin L$$, or vice versa. Since $$w \in a^*$$, in fact $$w = a^k$$ for some $$k$$, and so we need to prove the following:
If $$i \neq j$$ are natural numbers then there exists a natural number $$k$$ such that exactly one of $$i+k,j+k$$ is a power of 3.
Let $$a_i$$ be the smallest power of 3 which is at least $$i$$, and define $$a_j$$ similarly. If $$a_i \neq a_j$$, say $$a_i < a_j$$, then we can take $$k = a_i$$. So suppose $$a_i = a_j = a$$. Without loss of generality, $$i < j$$, and so $$i+a < j+a$$. The next power of 3 after $$i+a$$ is $$3(i+a)$$, and after $$j+a$$ is $$3(j+a)$$. Let $$k = 2i+3a$$. Then $$i + k$$ is a power of 3 by definition, but $$j+a < j + k < 3(j+a)$$ is not a power of 3.
Here is a simpler proof. We will show that for every $$\ell$$, the equivalence relation $$\equiv_L$$ has at least $$\ell$$ equivalence classes.
Given $$\ell$$, find $$n$$ such that $$3^{n+1} - 3^n \geq \ell$$. Consider the $$3^{n+1} - 3^n$$ words $$a^0,a^1,\ldots,a^{3^{n+1}-1-3^n}$$. I claim that they are pairwise inequivalent. Indeed, suppose $$0 \leq i < j \leq 3^{n+1} - 1 - 3^n$$. Let $$k = 3^{n+1} - j$$. Then $$3^n + 1 \leq k \leq k + i < k + j = 3^{n+1}.$$ In particular, $$k + i$$ is not a power of 3, whereas $$k + j$$ is a power of 3. Hence $$a^i a^k \notin L$$ whereas $$a^j a^k \in L$$, showing that these $$3^{n+1} - 3^n \geq \ell$$ are pairwise inequivalent. Hence there are at least $$\ell$$ equivalence classes.