# Number of equivalence classes

Given language $$L$$, why is it not necessarily true that the number of equivalence classes of $$L$$ is equal to the number of equivalence classes of $$L^R$$?

And for the private case that $$L$$ is regular, is that true?

Assuming you refer to Myhill-Nerode equivalence classes:

First notice, that for a non-regular language $$L$$, the number of classes is necessarily infinite. This is one direction of the Myhill-Nerode theorem.

Since regular languages are closed under reversal, it follows that for a non-regular language $$L$$, both $$L$$ and $$L^R$$ have the same number'' (namely, infinitely) of equivalence classes.

For the case of regular languages, the Myhill-Nerode relation is very right-biased'', since it relates to the existence of a separating suffix. This is why reversing the language may change the number of classes. For example, consider the language

$$L_k=\{w\in \{a,b\}^*: w_k=a\}$$ i.e. the language of words whose $$k$$-th letter is $$a$$.

It's easy to show that the number of classes for $$L_k$$ is roughly $$k$$ (maybe $$\pm 1$$).

However, the language $$L_k^R$$ of words whose $$k$$-before last letter is $$a$$, is known not to have a DFA with less than $$2^{k-1}$$ states (and hence it has $$\Omega(2^k)$$ classes).

Interestingly, reversal and congruence classes do have an interplay: if you take a DFA, reverse it, determinize it, reverse it again, determinize again, and remove all unreachable states, you will obtain a minimal DFA for the original language, which is exactly what the equivalence classes characterize. This is Brzozowski's algorithm.

• Thank you! got it.
– Ella
Jun 21, 2020 at 7:33