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?


1 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.

  • $\begingroup$ I think we can have two strings $a^p$ and $a^{p'}$ in same equivalence class. For example $a^{p} - a^{p'}$ has even length. It also works with the mentioned congruence $⇒uw∼vw$. But I guess your contradiction still works. $\endgroup$ Mar 8, 2016 at 20:29
  • $\begingroup$ It is $a^{p-p'}$ . Are you saying $a^c$ and $a^d$ can be in same equivalence class for $L$ if $c$ and $d$ are even numbers ($\neq 2$)? Can you give an example of two strings in same equivalence class for $L$? $\endgroup$ Mar 9, 2016 at 7:10
  • $\begingroup$ Just saying that for example relation defined that their concatenation has even length puts many primes in unary encoding into one equivalence class. And the equivalence stays if u concat any word to both of them. $\endgroup$ Mar 9, 2016 at 9:35
  • 1
    $\begingroup$ Equivalence says that if you concatenate two strings in an equivalence class with same suffix, then concatenated strings either are accepted or not accepted at the same time. On the basis of this we have proven that no two $a^p$ and $a^{p'}$ can be in same equivalence class. So, I can safely say I am not able to understand what you are saying. $\endgroup$ Mar 9, 2016 at 11:28
  • $\begingroup$ @Shreesh sorry to revive this old qustion but: why do you say: " if $a^p a^{q-p} \in L$ therefore $a^q a^{q-p} \in L $ resulting in $a^{p+i(q-p)} \in L $ ? $\endgroup$
    – zython
    Mar 23, 2018 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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