1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ By the way, your language is not regular. $\endgroup$ – Yuval Filmus Nov 21 '17 at 19:05
  • $\begingroup$ Why is his language not regular? $\endgroup$ – Michael Terry Nov 21 '17 at 23:30
  • $\begingroup$ @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\}$ $\endgroup$ – rotia Nov 25 '17 at 22:11
1
$\begingroup$

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

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.