Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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!
In order to check that these are the correct classes, you need to check three things:
Good luck!
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.
