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?

  • $\begingroup$ I dont know how you say, that the equivalence classes are different. So how to show that? $\endgroup$ – joee Nov 12 '18 at 11:20
  • $\begingroup$ Okay, that's a fair question. Hint: you're trying to show inequality of sets. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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