# 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 '18 at 11:20
• Okay, that's a fair question. Hint: you're trying to show inequality of sets. – Raphael Nov 12 '18 at 13:27

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.