Non-regularity of the set of primes in unary encoding using Myhill-Nerode

Question

I have found many proofs for this using pumping lemma, I'm curious of how to proof it via Myhill-Nerode theorem.

Suppose $L= \{a^p \mid p \text{ is prime}\}$ is regular. Then we have congruence such $u ∼ v ⇒ uw ∼ vw$ of finite index $k$, so it has $k$ equivalence classes. $L$ is union of some of its equivalence classes.

Let's choose $aa,aaa,...,a^{p_k},a^{p_{k+1}}$, where $p_k$ is $k$-th prime. Then, there exists $i,j$ from $\{1,...,k+1\}$, that $a^i∼a^j$. Now we should concatenate some word to $a^i$ and $a^j$, that one of the words is in $L$, while the other is not, but in contradiction, they are in the same equivalence class.

Any ideas?

Answer 1

We can prove that every string in $L$, $a^p$, $p$ is prime, is in its own different equivalence class. We simply cannot have two strings, $a^p$ and $a^{p'}$, both $p$ and $p'$ prime, in same equivalence class.

Assume $a^p$ and $a^q$, $q>p$, $p$ and $q$ prime, are in same equivalence class. Then since $a^{p}a^{q-p}=a^q$ is in $L$ therefore $a^qa^{q-p}=a^{2q-p}$ will be in $L$. Since $a^{p}a^{2q-2p}=a^{2q-p}$ is in $L$ therefore $a^qa^{2q-2p}=a^{3q-2p}$ will be in $L$. We will be able to show that $a^{p+i(q-p)}$ will be in $L$ for every $i \geq 0 $. But for $i=p$ there is a contradiction.

Factually speaking even $a^c$ and $a^d$ for composites $c$ and $d$ will be in different equivalence classes. If we assume $a^c$ and $a^d$, $d > c$, where $c$ and $d$ are not primes, are in same equivalence class, then we can similarly reach a contradiction. Even if we don't prove this, the number of equivalence classes is still infinite because each $a^p$ for prime $p$ is in different equivalence class.

Thus as number of equivalence classes for $L$ is infinite (because number of primes is infinite), therefore by Myhill-Nerode theorem $L$ is not a regular language.