Proving that language, with $|\Sigma|=1$, is irregular by Myhill–Nerode theorem

Question

We have $\Sigma =\{0\}$ and $$L=\{0^{2^n} \mid n\ge 0\}$$ How to prove that $L$ is irregular by using Myhill–Nerode theorem?

At other languages with $\Sigma >1$ we can usually separate the word or something like this with combination and this how we can show that two words are not at the same equivalent class....
But what we can do at this case?

Here what I tried:
Assuming that $i\ne j$, then $0^{2^i+1}$ is not at the same equivalent class with $0^{2^j+1}$, why?
Let mark: $p$ - the amount of $0$'s that we need to add to $0^{2^i+1}$ to be $0^{2^{i+1}}$, $q$ - same thing but with $j$ instead of $i$.
Of course $p\ne q$, hence:
$0^p\in 0^{2^i+1}$ but $0^p\notin 0^{2^j+1}$.

I'd like to know if I'm right at my and I should continue or try a different way...

Thank you!

Answer 1

Your idea is basically correct, but your argument could be written in a clearer way. You want to say that if $i \neq j$ then $0^{2^i+1},0^{2^j+1}$ are inequivalent. You propose to consider adding the word $0^{2^i-1}$ to both, obtaining $0^{2^{i+1}},0^{2^i+2^j}$. The first word is clearly in $L$, whereas the second isn't, though an argument is required (left to you). This shows that the infinite set $\{0^{2^i+1} : i \geq 0\}$ consists of pairwise inequivalent words (modulo $L$), so $L$ is not regular.

In fact, all words $0^n$ are pairwise inequivalent modulo $L$ – see if you can prove that. (The argument is very similar.)

For languages over a unary alphabet there is a simpler characterization. Let $L = \{0^n : n \in I\}$. Then $L$ is regular if and only if $I$ is eventually periodic, which means that for some $m \geq 1$, $n + m \in I$ iff $n + 2m \in I$. The set of powers of two is not eventually periodic since it has arbitrarily large "gaps". (A formal argument is similar to your proof.)