1
$\begingroup$

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!

$\endgroup$

1 Answer 1

1
$\begingroup$

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)^*. $$

$\endgroup$
2
  • $\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$ Feb 21, 2019 at 22:59
  • $\begingroup$ Yes, a language is regular iff there are finitely equivalence classes. $\endgroup$ Feb 22, 2019 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.