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

Question

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^+\}$?

Answer 1

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.

Answer 2

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.

Answer 3

If you have parsed the input $1^l 0$ then to get a string in the language, we must have l ≥ 1, and the only possibility is to produce $1^l 0^l$, so the prefix $1^l 0$ has only one possible suffix $0^{l-1}$. The set of possible suffixes is $\{ 0^{l-1} \}$, for l ≥ 1.

Now which other prefixes can be turned into a string of the language by adding a string of the form $0^{l-1}$? That's the strings where we have k more 1s and k more 0s, so $1^{l+k} 0^{1+k}$. These are exactly the strings where adding l-1 more 0's produces a string in L and adding any other suffix doesn't: $1^{l+k} 0^{1+k} 0^{l-1}$ = $1^{l+k} 0^{l+k}$ which is in the language.

I personally find it easier to find the possible sets of suffixes. There are quite obviously three kinds of suffix sets: If you have parsed k 1's so far, you can add another n 1's for a total of n+k 1's, and then n+k 0's. So you have a set of suffixes $\{ 1^n 0^{k+n} \}$, n ≥ 0. For each different k, you get a different set of suffixes.

If you have parsed k 1's and n 0's, for 1 ≤ n ≤ k, then you cannot add another k; to get a string in the language you need to add exactly $0^{k-n}$, one choice only. k-n can be any integer, so for every different value of n-k we get a different set containing exactly one suffix.

And finally if we parsed k 1's and either n > k 0's, or 1 ≤ n ≤ k 0's followed by a 1, or either followed by more symbols, then there is no way to get a string in L, so the set of suffixes is the empty set.

In total, we have an infinite number of different sets of suffixes (which implies L is not regular). If we only wanted to show that L is not regular, we didn't have to calculate all the sets precisely. It is enough to state that $1 1^k 0$ can only be extended to a string in L by adding k 0's, so we have an infinite number of sets of suffixes, and an infinite set of equivalence classes, and no regular languages, even if we didn't bother to figure out these sets and strings exactly.