1
$\begingroup$

I am told to find the equivalence classes of the Myhill–Nerode relation of the language $\{0^n1^n \mid n \in \mathbb{N}\}$. For one, I know it has an infinite number of equivalence classes given that it's a non-regular language. Im not sure how to find all the equivalence classes and show how I got those equivalence classes.

$\endgroup$

1 Answer 1

3
$\begingroup$

Here is how to think of this question. The equivalence relation is determined by which extensions of the current word belong to the language. There are three cases:

  • The current word is not a prefix of any word in the language. This happens if either the word is not in $0^*1^*$ at all, or if it is of the form $0^n1^m$ but $m > n$.
  • There is a unique extension of the current word which is in the language. This happens if the word is of the form $0^n1^m$ with $m \neq 0$ (and, to exclude the case above, $m \leq n$).
  • There are multiple extensions of the current word which are in the language. This happens for words in $0^*$.

Let us now get into more detail:

  • If $w = 0^n$, then we can extend $w$ to a word in the language by adding $0^m 1^{n+m}$ for arbitrary $m \in \mathbb{N}$. Note that this set of extensions is different for every $n$.
  • If $w = 0^n1^m$ where $0 < m \leq n$ then there is a unique way to extend $w$ to a word in the language, namely by adding $1^{n-m}$.
  • Otherwise, $w$ cannot be extended to a word in the language.

Accordingly, the equivalence classes are:

  • $\{0^n\}$ for every $n \in \mathbb{N}$.
  • $\{0^{n+m} 1^m : m \in \mathbb{N}\}$ for every $n \in \mathbb{N}$.
  • Everything else.
$\endgroup$
1
  • $\begingroup$ Understood...thank you. $\endgroup$ Mar 2, 2021 at 11:20

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.