# Irregularity of $\{a^p : p \text{ prime}\}$ using Myhill–Nerode

Consider the language $$L = \{2^k : k \text{ is prime}\}.$$ This language contains, for example, $$2^3=222$$, $$2^5=22222$$, $$2^7=2222222$$, and so on.

I know that $$L$$ is irregular and so there must exist a set of strings that are pairwise distinguishable with respect to $$L$$, but I'm struggling to come up with such a set of strings. Any help would be appreciated!

• Maybe I didn't understand something, but $\Sigma^*$ is regular, but still follows your definition. Sep 29 '21 at 4:51

You can choose $$2^*$$ as your set of words. Indeed, consider the words $$2^a,2^b$$, where $$a < b$$. If these words are indistinguishable then for all $$c \geq 0$$, $$a + c$$ is prime iff $$b + c$$ is prime. Since there are infinitely many primes, we can find a prime $$p \geq a$$. Let $$c_1 = p-a$$. Since $$p$$ is prime, so is $$b + c_1 = p + (b-a)$$. Choosing $$c_2 = p-a+(b-a)$$, we similarly get that $$b + c_2 = p + 2(b-a)$$ is prime. Continuing in this fashion, we see that $$p + k(b-a)$$ is prime for all $$k \geq 0$$. In particular, $$p + p(b-a)$$ should be prime. But $$p + p(b-a) = p(b-a+1)$$ clearly isn't prime. This contradiction shows that $$2^a,2^b$$ are distinguishable.