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.

| cite | improve this answer | |
  • $\begingroup$ Thank you! got it. $\endgroup$ – Ella Jun 21 at 7:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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