How to find Myhill-Nerode equivalence classes, algorithmically?

Question

Say I have a regular expression given, or a language given in set form.

Examples:

$$ L= \{ w \in \{a,b\}^* | w \ \text{ matches} \ \ a^*b^*(bab)^*\} \\ L = \{ w | count_a(w) = 5 \} \\ L= \{ w \in \{a,b\}^* | aab \ \ \text{is substring of w\}} $$

Is there an algorithmic-like approach to finding the equivalence classes or do I have to try out different strings and test them with respect to the Nerode relation ?

---

Now my question:

How do I quickly find the equivalence classes for a given language ?

Whats the trick/intuition ?

Answer 1

Are you familiar with the DFA minimization algorithm? This is probably the easiest way to compute the Myhill-Nerode equivalence classes.

Given a regular expression, it should be straight-forward to construct a DFA.

Answer 2

For each word $u$, let $$ u^{-1}L = \{v\in A^*\mid uv \in L\} $$ These languages can be computed recursively by using the following formulas, where $u, v \in A^*$ and $a \in A$: \begin{align*} (uv)^{-1}L &= v^{-1}(u^{-1}L) \\ u^{-1}(L_1 \cup L_2) &= u^{-1}L_1 \cup u^{-1}L_2\\ u^{-1}(L_1 \setminus L_2) &= u^{-1}L_1 \setminus u^{-1}L_2\\ u^{-1}(L_1 \cap L_2) &= u^{-1}L_1 \cap u^{-1}L_2\\ a^{-1}(L_1L_2) &= \begin{cases} (a^{-1}L_1)L_2 &\text{if $1 \notin L_1$,}\\ (a^{-1}L_1)L_2 + a^{-1}L_2 &\text{if $1 \in L_1$}\\ \end{cases}\\ a^{-1}L^* &= (a^{-1}L)L^* \end{align*} For instance, let $A = \{a, b\}$ and $L = A^*aabA^*$. Then \begin{align*} 1^{-1}L &= L \\ a^{-1}L &= A^*aabA^* \cup abA^* = L_1 \\ b^{-1}L &= L \\ a^{-1}L_1 &= a^{-1}(A^*aabA^*) \cup a^{-1}(abA^*) = A^*aabA^* \cup abA^* \cup bA^* = L_2 \\ b^{-1}L_1 &= b^{-1}(A^*aabA^*) \cup b^{-1}(abA^*) = A^*aabA^* = L \\ a^{-1}L_2 &= a^{-1}(A^*aabA^*) \cup a^{-1}(abA^*) \cup a^{-1}(bA^*) = A^*aabA^* \cup abA^* \cup bA^* = L_2 \\ b^{-1}L_2 &= b^{-1}(A^*aabA^*) \cup b^{-1}(abA^*) \cup b^{-1}(bA^*) = L \cup A^* = A^* \\ a^{-1}L_3 &= a^{-1}A^* = A^*\\ b^{-1}L_3 &= b^{-1}A^* = A^* \end{align*} Therefore, there are four Nerode classes, associated to the words $1$, $a$, $aa$ and $aab$.