1
$\begingroup$

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 ?

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.