2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

$\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.)

$\endgroup$
5
  • $\begingroup$ 1|2 Hey, thanks for that quick answer. The problem what I have is to understand, why for example this $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\} \,.$ and this $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\} \,.$ are equivalent. $\endgroup$
    – Marie.L
    Feb 4, 2019 at 21:01
  • $\begingroup$ 2|2 If we would use the definition with $x=73a^2$ and $y=73a^3$ and a $z=a7b$, then we get $xz = 73a^2a7b = 73a^37b$ (that's in the language) and $yz = 73a^3a7b = 73a^47b$ (that's not in the language) so both would be not equivalent. I know I'm using the definition incorrectly but there is my thinking problem xD. $\endgroup$
    – Marie.L
    Feb 4, 2019 at 21:01
  • $\begingroup$ No, they are NOT equivalent. $\left[73 a^2\right]_{\equiv_{B}}$ and $\left[73 a^3\right]_{\equiv_{B}}$ are two different classes. $\left[73 a^2\right]_{\equiv_{B}}$ is one class that contains only one word, $73a^2$. $\left[73 a^3\right]_{\equiv_{B}}$ is another class that contains only one word, $73a^3$. You should view these two classes as totally unrelated to each other. In other words, the only relation between the two is that as sets, they are disjoint. $\endgroup$
    – John L.
    Feb 4, 2019 at 21:14
  • $\begingroup$ Case 3 is completely different from case 1 or case 2. There is only one equivalent class in case 1. There is only one equivalent class in case 2. There are infinitely many equivalent classes in case 3, each of which contains a single word. $\endgroup$
    – John L.
    Feb 4, 2019 at 21:19
  • $\begingroup$ Ahhhh, that's make sense now $\endgroup$
    – Marie.L
    Feb 4, 2019 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.