# Myhill-Nerode equivalence classes of $\{1^n0^n\}$

I have the following task and its solution.

Question

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.

Solution

• $$[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.

• 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\}$ – Lisa.Neust Jan 30 '19 at 14:32
• 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. – Lisa.Neust Jan 30 '19 at 14:35
• We don't have two classes with the exact same set of suffixes. It's OK to have a suffix common to two classes. – Yuval Filmus Jan 30 '19 at 14:40