# Myhill–Nerode equivalence classes for the language $b^ia^{5j}$

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!

## 2 Answers

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!

• So how would that look in my case? May 9 at 10:56
• It's your exercise... May 9 at 11:44
• 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? May 9 at 11:54

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.