I'm doing a problem where I need to find the $≡_A$ equivalence classes of the language $$A = \{ 0^{n}x \mid n \in \mathbb Z^+, x \in \{0, 1\}^*, \text{ and } \#_0(x) ≥ n \}. $$

The best way I've learned to find the equivalence classes from a formal language is to create an automation and minimize it. Is there a conventional way of finding the equivalence classes of a language more quickly and intuitively? Because I do not know the DFA for this problem. Thanks for the help!


Your language is $01^*0(0+1)^*$, i.e., all words starting with 0 and containing at least one more 0.

Indeed, a word of the form $0y0z$ is in $A$ since we can take $n=1$ and $x = y0z$. Conversely, if $w = 0^nx \in A$ then $w$ contains at least $2n \geq 2$ many 0's, and starts with a 0.

Therefore the Myhill–Nerode equivalence classes of your language are: $$ \epsilon, 1(0+1)^*, 01^*, 01^*0(0+1)^*. $$

  • $\begingroup$ Since there are finite number of equivalence classes, does that make the language regular? Also what would change of the equivalence classes if #0(x)<n instead of >n $\endgroup$ – James Pekon Feb 21 at 22:59
  • $\begingroup$ Yes, a language is regular iff there are finitely equivalence classes. $\endgroup$ – Yuval Filmus Feb 22 at 3:31

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.