Let $L$ be a language over $\{0,1\}$ whose Nerode equivalence classes are:
$$
\{w|\#_0(w)\mod2=0\quad\land\quad \#_1(w)\mod2=0\}\\
\{w|\#_0(w)\mod2=0\quad\land\quad \#_1(w)\mod2=1\}\\
\{w|\#_0(w)\mod2=1\quad\land\quad \#_1(w)\mod2=1\}\\
\{w|\#_0(w)\mod2=1\quad\land\quad \#_1(w)\mod2=0\}
$$
($\#_0(w)\mod2=0$ means that the number of zeroes in word $w$ is even).Also $\epsilon \in L, 0,1,1110\notin L$. Find DFA for the language.
First because there's a finite number of eq. classes by Nerode theorem we know that $L$ is regular so DFA exists for the language.
The solution to the problem is:
But I don't understand how the DFA accommodates all possible words in $L$.
1) For example what about $111$? It had even number of $0$'s and uneven number of $1$'s so it belongs to the second eq.class. But I don't see how we can arrive to this word using the DFA above.
2) What about the word $00011$? It belongs to the fourth equivalence class but I don't see how to arrive at this word using the DFA.
Best Answer
Not every equivalence class belongs to the language, otherwise the language would always be $\Sigma^*$. Since $\varepsilon \in L$ and $0,1,1110 \notin L$, we know that $L$ equals the first equivalence class. Therefore your examples are not counterexamples.