I have the following task and its solution.


Given the language

$$ A \triangleq\left\{1^{n} 0^{n} \mid n \in \mathbb{N}\right\} \text { with } \Sigma_{A} \triangleq\{1,0\}, $$

give all equivalence classes of the Myhill-Nerode relation.


  • $[1^k]_{\equiv A} = \{1^k\}$ for $k \in \mathbb N$.
  • $[1^\ell0]_{\equiv A} = \{1^{\ell+i-1} 0^i \mid i \geq 1\}$ for $\ell \in \mathbb N^+$.
  • $[0]_{\equiv A} = \{ 0x, 1^n 0^m, x01 y \mid x,y \in \Sigma_A^* \land n,m \in \mathbb N^+ \land m > n \}$.

What are they doing in the second bullet of the solution?

The first and third bullets are clear. In the first they construct the equivalence classes of all $1$'s including $\lambda$.

In the third bullet they construct just one equivalence class with all the words which are not in the language $A$.

But what are they doing in the second bullet? What does the exponent $\ell+i-1$ mean? Why don't they write $[1^n0^m]_{\equiv A} = \{1^n 0^m \mid n,m \in \mathbb N^+\}$?


I think it makes sense to answer your subquestions out of order.

Why they don't write $[1^n0^m] = \{1^n 0^m | n,m \in N^+\}$

They're supposed to be equivalence classes. $[1^n0^m]$ would break up lots of classes, and duplicate lots of the states from line 3.

What does the Exponent $n+i-1$ mean?

Firstly, $n+i-1 \ge i$, so there are at least as many $1$s as $0$s.

Secondly, $n$ is the parameter which defines the class.

So $\left[1^{\mathrm{l}}0\right]_{\equiv \mathrm{A}}$ is the set of states which need $0^{l-1}$ to reach the accepting state.


There are infinitely many equivalence classes:

  • For each $k \geq 0$, the equivalence class of $1^k$, which consists only of $1^k$.
  • For each $\ell \geq 1$, the equivalence class of $1^\ell 0$, which consists of $1^{\ell-1+i} 0^i$ for all $i \geq 1$.
  • All other words (the equivalence class of $0$): words beginning with $0$, words containing a substring $01$, and words of the form $1^n0^m$ with $m > n$.

The last equivalence class is easiest to understand: it consists of those words which cannot be extended to words in $A$.

The equivalence class of $1^\ell 0$ consists of all words whose only extension in $A$ is by $0^{\ell-1}$.

Finally, $1^k$ can be extended to a word in $A$ by adding $1^j 0^{k+j}$ for arbitrary $j \geq 0$.

Using this, it is easy to check that all of these equivalence classes are actually distinct. In particular, it is definitely not true that all words of the form $1^n 0^m$ belong to the same equivalence class, if only since some of them belong to $A$ and some don't.

  • $\begingroup$ thanks for your answer. If I understand this right than each prefix of a word only allows one suffix to be completed in that language. So $[1^0] = \{ \lambda \}$ or $[1^1] = \{ 1 \}$ and prefix $0$ or $[1^2] = \{ 1^2 \}$ and prefix $0^2$ and so on. But if we look at the second bullet , we have does equivalence class: $ [a b]=\quad L \quad \quad $ Suffix: $ \quad\{\epsilon\} $ $ \left[a^{2} b\right]=\left\{a^{2} b, a^{3} b^{2}, a^{4} b^{3}, \ldots\right\} \quad $ Suffix : $ \quad\{b\} $ . . . $[1^\ell0]_{\equiv A} = \{1^{\ell+i-1} 0^i \mid i \geq 1\}$ $\endgroup$ – Lisa.Neust Jan 30 '19 at 14:32
  • $\begingroup$ But than we have two classes with the same suffix is this possible? I'm so sry for my bad English, I'm learning it since 4 month, but I hope you can understand. $\endgroup$ – Lisa.Neust Jan 30 '19 at 14:35
  • $\begingroup$ We don't have two classes with the exact same set of suffixes. It's OK to have a suffix common to two classes. $\endgroup$ – Yuval Filmus Jan 30 '19 at 14:40

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.