How I can find all equivalence classes by Myhill-Nerode?

Question

first of all I'm sorry for my bad English and second I'm sorry for my mistakes of understanding the following topic, I still going to school and learning this for interest.

The topic is Myhill-Nerode and the equivalence classes of a regular or non regular language.

I know that every element of a equivalence class by Myhill-Nerode fulfills this property:

$ \equiv_{A} \triangleq\{(x, y) | \forall z \in \Sigma^{*} \cdot(x z \in A \leftrightarrow y z \in A)\} $

If I understand this right, than a equivalence class consist of element (words) $x$ which we can expand with a word $y$ but for all words $x$ and $y$ of the same class must apply, adding a word $z$ to them both must be in or out of the language.

Hope that is right until now.

Now I will show you my problem:

I have the language (its from a book):

$ \mathrm{B} \triangleq\left\{73 \mathrm{a}^{n} 7 \mathrm{b}^{\mathrm{m}} | \mathrm{n}, \mathrm{m} \in \mathbb{N} \wedge \mathrm{n}=\mathrm{m}+2\right\} $ with $ \Sigma_{\mathrm{M}} \triangleq\{\mathrm{a}, \mathrm{b}, 3,7\} $

And a complete solution:

$1: [\lambda]\equiv_{B}=\{\lambda\} $

$2: [7]\equiv_{B}=\{7\} $

$3: \left[73 a^{k}\right] \equiv_{B}=\left\{73 a^{k}\right\} $ für $ k \in \mathbb{N} $

$4: \left[73 a^{l+2} 7\right] \equiv_{B} =\left\{73 \mathrm{a}^{\imath+2+n} 7 \mathrm{b}^{\mathrm{n}} | \mathrm{n} \in \mathbb{N}\right\} \quad $ für $ l \in \mathbb{N} $

$5: [3]_{\equiv \mathrm{B}}=\Sigma^{*} \backslash\left([\lambda]_{\equiv \mathrm{B}} \cup[7]_{\equiv \mathrm{B}}\right. \cup\left(\bigcup_{k \in \mathbb{N}}\left[73 a^{k}\right] \equiv_{B}\right) \cup \left(\bigcup_{\mathfrak{l} \in \mathbb{N}}\left[73 \mathrm{a}^{\ l+ 2} 7\right] \equiv_{\mathrm{B}}\right) ) $

So in $1$ they build a class of the empty word $\lambda$ and $z = B$ has to be the language by her self to be in the language?

In $2$ they build they build the class of $7$ and z has to be something like this $ z = \left\{3 \mathrm{a}^{n} 7 \mathrm{b}^{\mathrm{m}} | \mathrm{n}, \mathrm{m} \in \mathbb{N} \wedge \mathrm{n}=\mathrm{m}+2\right\}$ to be in the language.

In $3$ they build a class or better infinitely many classes. But here is my problem. I cannot find a $z$ which is working for all classes.

For example we have the words $x_i$ and $z_i$

$x_1 = 73 \to z_1= {a}^{n+2}7b^n$ with $n\in N$

$x_2 = 73a \to z_2= {a}^{n+1}7b^n$ with $n\in N$

$x_3 = 73a^2 \to z_3= {a}^{n}7b^n$ with $n\in N$

$x_4 = 73a^3 \to z_4= {a}^{n}7b^n+1$ with $n\in N$

and so on.

But why is this ok? I Mean they are 2 words in this class for example $x_1$ and $x_2$ who $x_2$ would not be in $B$ with $z_1$.

I hope you can tell me on a simple and understanding way how those classes by Myhill work and how i can find them without making big mistakes.

Answer 1

$\Bbb N$ denotes the set of natural numbers, that is, the set $\{0,1,2, \cdots\}$. If $\Bbb N$ is the set of positive integers, the treatment will be roughly the same.

---

So in $1$ they build a class of the empty word $\lambda$ and $z = B$ has to be the language by her self to be in the language?

Since the above paragraph in the question, $z=z(C)$ is understood/redefined to be the set of words such that Cz is a subset of $B$, given a set of words $C$. That is, $cw\in b$ for any $c\in C$ and $w\in z$.

With the above understanding, yes, $z([\lambda]_{\equiv_{B}})=z(\{\lambda\})=B.$

$3: \left[73 a^{k}\right]_{\equiv_{B}}=\left\{73 a^{k}\right\} $ for $ k \in \mathbb{N} $

Case 3 gives one equivalent class for each $k\in\Bbb N$. It lists infinitely many equivalent classes as the following, each with different $z$.

• Letting $k=0$, we have $\left[73\right]_{\equiv_{B}}=\left\{73\right\}\,.$
• Letting $k=1$, we have $\left[73 a^1\right]_{\equiv_{B}}=\left\{73 a^1\right\}\,.$
• Letting $k=2$, we have $\left[73 a^2\right]_{\equiv_{B}}=\left\{73 a^2\right\}\,.$
• Letting $k=3$, we have $\left[73 a^3\right]_{\equiv_{B}}=\left\{73 a^3\right\}\,.$
• $\vdots$

Their $z$'s are the following, which are more or less listed in the question.

• $z\left(\left[73\right]_{\equiv_{B}}\right)=z\left(\left\{73 \right\}\right)=\left\{a^n7b^m \mid n,m\in \Bbb{N} \wedge n=m+2\right\} \,.$
• $z\left(\left[73 a^1\right]_{\equiv_{B}}\right)=z\left(\left\{73 a^1\right\}\right)= \left\{a^n7b^m \mid n,m\in \Bbb{N} \wedge n=m+1\right\} \,.$
• $z\left(\left[73 a^2\right]_{\equiv_{B}}\right)=z\left(\left\{73 a^2\right\}\right)=\left\{a^n7b^m \mid n,m\in \Bbb{N} \wedge n=m\right\} \,.$
• $z\left(\left[73 a^3\right]_{\equiv_{B}}\right)=z\left(\left\{73 a^3\right\}\right)=\left\{a^n7b^m \mid n,m\in \Bbb{N} \wedge n=m-1\right\} \,.$
• $\vdots$

Once you have understood the above, it should be easy to figure out case 4 and the rest of the given solution. You did have a pretty good understanding of the Myhill-Nerode equivalence classes.

---

Here is another way to write the same solution in the question.

$1: [\lambda]_{\equiv_{B}}=\{\lambda\} $

$2: [7]_{\equiv_{B}}=\{7\} $

$3: \left[73\right]_{\equiv_{B}}=\left\{73\right\}$

$4: \left[73a\right]_{\equiv_{B}}=\left\{73a\right\}$

$5: \left[73a^2\right]_{\equiv_{B}}=\left\{73a^2\right\}$

$6: \left[73a^3\right]_{\equiv_{B}}=\left\{73a^3\right\}$

$\vdots$

$\infty+1: \left[73 a^2 7\right]_{\equiv_{B}} =\left\{73 a^{2+n} 7 b^{n} \mid n \in \mathbb{N}\right\}$

$\infty+2: \left[73 a^3 7\right]_{\equiv_{B}} =\left\{73 a^{3+n} 7 b^{n} \mid n \in \mathbb{N}\right\}$

$\infty+3: \left[73 a^4 7\right]_{\equiv_{B}} =\left\{73 a^{4+n} 7 b^{n} \mid n \in \mathbb{N}\right\}$

$\infty+4: \left[73 a^5 7\right]_{\equiv_{B}} =\left\{73 a^{5+n} 7 b^{n} \mid n \in \mathbb{N}\right\}$

$\vdots$

$2\infty+1: [3]_{{\equiv B}}=\Sigma^{*} \setminus\left([\lambda]_{\equiv B} \cup[7]_{\equiv B} \cup\left(\bigcup_{k \in \Bbb{N}}\left[73 a^{k}\right]_ {\equiv_{B}}\right) \cup \left(\bigcup_{k \in \Bbb{N}}\left[73a^{k+ 2} 7\right]_{\equiv_B}\right)\right)\,. $

---

Exercise. 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. (Check here for an answer.)