How to find the equivalence classes of a regular language

Given a language $L=\{ 0^m1^n | m \neq n \}$ over $\Sigma = \{ 0,1 \}$, how would one go about characterizing the equivalence classes of this language?
I know there isn't a formal algorithm for that, but still, can some steps always be taken?

• By the way, your language is not regular. Commented Nov 21, 2017 at 19:05
• Why is his language not regular? Commented Nov 21, 2017 at 23:30
• @MichaelTerry I think that if you could have a DFA for this language, then, you could have another one for the complement of the languange by turning the accepting states into nonaccepting states and viceversa. The complement is the non regular language $\{0^n1^n\}$ Commented Nov 25, 2017 at 22:11

You have to be creative. In this case, the equivalence classes are:

• $X_a = \{0^a\}$ for $a \geq 0$.
• $Y_a = \{0^{n+a} 1^n : n > 0\}$ for $a \geq 0$.
• $Z = \{0^n 1^m : m > n \}$.
• $W = \{w : w \text{ contains } 10\}$.

We can construct an infinite DFA to show that each of these classes consists of equivalent words:

• The initial state is $X_0$.
• The accepting states are $X_a,Y_a$ for $a \neq 0$ and $Z$.
• $\delta(X_a,0) = X_{a+1}$, $\delta(X_0,1) = Z$, $\delta(X_{a+1},1) = Y_a$.
• $\delta(Y_a,0) = W$, $\delta(Y_0,1) = Z$, $\delta(Y_{a+1},1) = Y_a$.
• $\delta(Z,0) = W$, $\delta(Z,1) = Z$.
• $\delta(W,0) = \delta(W,1) = W$.

This also shows that the classes cover all of $\Sigma^*$. Finally, in order to show that these are the equivalence classes, we need to show that any two classes have a separating word:

• $X_a,X_b$: $1^a$.
• $X_a,Y_a$: $0$.
• $X_a,Y_b$: $0$.
• $X_a,Z$: $1^a$.
• $X_a,W$: $0$.
• $Y_a,Y_b$: $1^a$.
• $Y_a,Z$: $1^a$.
• $Y_a,W$: $1^{a+1}$.
• $Z,W$: $\epsilon$.