2
$\begingroup$

I have to find equivalence classes for different languages based on Myhill-Nerode. I'm struggling a little bit finding these equivalence classes; for example, the language $L=\{b^*a^n\mid n≡0\pmod5\}$ with alphabet $\{a,b\}$.

My first solution would be: $[\epsilon],[b^∗],[b^∗a],[b^∗aa],[b^∗aaa],[b^∗aaaa]$.

Would these be the correct classes? If not, i would appreciate any help!

$\endgroup$

2 Answers 2

2
$\begingroup$

In order to check that these are the correct classes, you need to check three things:

  1. Any two words in the same class are equivalent.
  2. Any two words in different classes are inequivalent.
  3. Every word belongs to one of the classes.

Good luck!

$\endgroup$
3
  • $\begingroup$ So how would that look in my case? $\endgroup$ May 9 at 10:56
  • 5
    $\begingroup$ It's your exercise... $\endgroup$ May 9 at 11:44
  • $\begingroup$ Look at the last condition: "Every word belongs to one of the classes". Which of your classses does baaaaaa belong to? Which of your classes does ababa belong to? $\endgroup$
    – gnasher729
    May 9 at 11:54
2
$\begingroup$

The Myhill-Nerode relation with respect to a given language $L \subseteq \Sigma^*$ is an equivalence relation on $\Sigma^*$ and hence gives a partition of $\Sigma^*$. Because this is a partition, the equivalence classes must be pairwise disjoint and their union must be all of $\Sigma^*$. Two strings $x, y \in \Sigma^*$ belong to different equivalence classes if and only if there is some string $z \in \Sigma^*$ that is a distinguishing extension of $x$ and $y$ in the sense that exactly one of $xz$ and $yz$ belongs to $L$.

When an equivalence class is written as $[x]$, the string $x \in \Sigma^*$ has been chosen as the representative element for this class. Thus, when you write $[\epsilon]$, that's the equivalence class represented by the empty string $\epsilon$. But your notation $[b^*]$ is not clear because $b^*$ is a set (rather than a single string) and denotes the set of all strings that contain zero or more $b$'s. Perhaps you meant the equivalence class $[b]$. As shown in the next paragraph, the empty string $\epsilon$ and the string $b$ must belong to the same equivalence class, so your solution that puts $[\epsilon]$ and $[b]$ as different equivalence classes is incorrect.

Let $L = \{b^i a^{5j}: i \ge 0, j \ge 0\}$. We now show that $\epsilon z \in L$ if and only if $bz \in L$, for all $z \in \Sigma^*$. (a) Suppose $z \in \Sigma^*$. If $\epsilon z \in L$, then $z = b^i a^{5j}$ for some $i \ge 0, j \ge 0$, whence $b z = b^{i+1}a^{5j} \in L$. (b) Conversely, suppose $bz \in L$. Then $bz = b^i a^{5j}$ for some $i \ge 1, j \ge 0$, whence $z = b^{i-1} a^{5j}$, where $i \ge 0, j \ge 0$. Hence, $\epsilon z = z \in L$. It follows that $\epsilon z \in L$ whenever $bz \in L$.

It appears that $\epsilon$ and $a^5$ belong to different equivalent classes because they have $b$ as a distinguishing extension, i.e. $\epsilon b \in L$ and $a^5 b \notin L$. Consider drawing a DFA with seven states that accepts $L$, and for each state $q$, define the subset $L_q$ to be the set of all strings in $\Sigma^*$ that take the machine from the start state to the state $q$. The subsets will give a partition of $\Sigma^*$. Check if the elements in a subset $L_q$ are pairwise indistinguishable, and that elements in different subsets are distinguishable. If the DFA has a minimal number of states, the subsets would give the equivalence classes. Alternatively, you can construct the equivalence classes by starting with a string $x_1$, finding all elements indistinguishable from it to get $[x_1]$, then start with a string in $\Sigma^* - [x_1]$, and find its class, and so on.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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