Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
2 deleted 69 characters in body; edited title
source | link

Equivalence classes by Myhill-Nerode , what are they doing in this given solution?equivalence classes of $\{1^n0^n\}$

I have the following task (1) and its solution (2)

(1) Given is the language

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

Give all equivalence classes of the Myhill-Nerode relation.

(2)Question

$ \left[1^{\mathrm{k}}\right]_{\equiv \mathrm{A}}=\left\{1^{\mathrm{k}}\right\} \quad $ with $ \mathrm{k} \in \mathbb{N} $

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.

$\left[1^{\mathrm{l}}0\right]_{\equiv \mathrm{A}}=\{{1}^{l+i-1}0^i|i\geq 1 \} \ with\ l \in \mathbb{N}^{+}$Solution

$ [0]_{\equiv_{A}}=\left\{0 x, 1^{n} 0^{m}, x 01 y | x, y \in \Sigma_{A}^{*} \wedge n, m \in \mathbb{N}^{+} \wedge m>n\right\} $

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

My question is: WhatWhat are they dodoing in line 2the second bullet of the solution (2). The?

The first and third linebullets are clear. In the first they buildconstruct the equivalence classes of all $1$'s includeincluding $\lambda$. In

In the third linebullet they buildconstruct just one equivalence class with all the words whowhich are not in the language $A$. But

But what are they doing in line 2the second bullet? What does the Exponentexponent $n+i-1$$\ell+i-1$ mean? Why they don't they write $[1^n0^m] = \{1^n 0^m | n,m \in N^+\}$

Best regards

Lisa$[1^n0^m]_{\equiv A} = \{1^n 0^m \mid n,m \in \mathbb N^+\}$?

Equivalence classes by Myhill-Nerode , what are they doing in this given solution?

I have the following task (1) and solution (2)

(1) Given is the language

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

Give all equivalence classes of the Myhill-Nerode relation.

(2)

$ \left[1^{\mathrm{k}}\right]_{\equiv \mathrm{A}}=\left\{1^{\mathrm{k}}\right\} \quad $ with $ \mathrm{k} \in \mathbb{N} $

$\left[1^{\mathrm{l}}0\right]_{\equiv \mathrm{A}}=\{{1}^{l+i-1}0^i|i\geq 1 \} \ with\ l \in \mathbb{N}^{+}$

$ [0]_{\equiv_{A}}=\left\{0 x, 1^{n} 0^{m}, x 01 y | x, y \in \Sigma_{A}^{*} \wedge n, m \in \mathbb{N}^{+} \wedge m>n\right\} $

My question is: What are they do in line 2 of the solution (2). The first and third line are clear. In the first they build the equivalence classes of all $1$'s include $\lambda$. In the third line they build just one equivalence class with all the words who are not in the language $A$. But what are they doing in line 2? What does the Exponent $n+i-1$ mean? Why they don't write $[1^n0^m] = \{1^n 0^m | n,m \in N^+\}$

Best regards

Lisa

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

1
source | link

Equivalence classes by Myhill-Nerode , what are they doing in this given solution?

I have the following task (1) and solution (2)

(1) Given is the language

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

Give all equivalence classes of the Myhill-Nerode relation.

(2)

$ \left[1^{\mathrm{k}}\right]_{\equiv \mathrm{A}}=\left\{1^{\mathrm{k}}\right\} \quad $ with $ \mathrm{k} \in \mathbb{N} $

$\left[1^{\mathrm{l}}0\right]_{\equiv \mathrm{A}}=\{{1}^{l+i-1}0^i|i\geq 1 \} \ with\ l \in \mathbb{N}^{+}$

$ [0]_{\equiv_{A}}=\left\{0 x, 1^{n} 0^{m}, x 01 y | x, y \in \Sigma_{A}^{*} \wedge n, m \in \mathbb{N}^{+} \wedge m>n\right\} $

My question is: What are they do in line 2 of the solution (2). The first and third line are clear. In the first they build the equivalence classes of all $1$'s include $\lambda$. In the third line they build just one equivalence class with all the words who are not in the language $A$. But what are they doing in line 2? What does the Exponent $n+i-1$ mean? Why they don't write $[1^n0^m] = \{1^n 0^m | n,m \in N^+\}$

Best regards

Lisa