# 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

## 1 Answer

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.