[Math] Finding Nerode equivalence classes

formal-languagesregular-language

How am I supposed to find the equivalence classes of a Language?
What should I think?

For instance, having a language

$$L =\{a^n b^m \mid n,m \ge 0, (m+n) \bmod2=0)\}$$

I can have:

  • $[a^n]$ with $n$ even. Whatever word i add, the word belongs to $L$
  • $[a^n]$ with $n$ odd. _There are no chances that, adding a word $z$ $i$
    obtain something that belongs to $L$ (i should add another odd number
    of letters, which is not possible). _
  • $[a^nb^m]$ $n$ is even $m$ is odd or viceversa. If and only if i add an odd number if $b$'s I obtain a word in the language.
  • $[a^nb^m]$ n is even m is even or n is odd m is odd.
    If and only if i add an even number if b's I obtain a word in the
    language.

Am I right?
Is there an algorithm to find this equivalence class in more general/difficult cases?

Best Answer

Your general way of thinking seems to be right, but your explanations of the first two equivalence classes is off.

If you have seen an even number of as, it is not true that you end up in $L$ no matter what you add. For example if you have seen is aa and the rest of the input is b, the entire string aab is not in $L$.

Conversely, if you have seen an odd number of as, all is not lost. For example, if you have seen aaa, you can still end up in $L$ if the rest of the input is abb.

(Are you perhaps expecting that the word you add must itself be in $L$? There's no such requirement).

In the two $\mathtt a^n\mathtt b^m$ classes you should specify that they apply only when $m\ge 1$.

There's in fact a fifth equivalence class, consisting of strings that are not prefixes of any word in $L$ such as aaba or abc.

A different way of describing the four "live" equivalence classes would be that each of them is characterized by the answers to the two questions: Have I seen an even or an odd number of symbols yet? and Have I begun seeing bs yet?

There's no algorithm for finding the equivalence classes when, as here, the description of the language you have to work from is a free-form human-readable description.

However, if you have a formal specification of a regular language (such as a regular expression, a regular grammar, or a finite automaton), then the equivalence classes correspond exactly to the reachable states of a minimized DFA, and you can use standard algorithms to construct that.

Related Question