# DFA and equivalence classes: counting odd numbers of b's

I am studying for an exam and found an exercise about finding the equivalence classes for $L=a^*ba^*(ba^*ba^*)^*$, the language over $\{a,b\}^*$ with an odd number of b's.

We found three equivalence classes: $[a^*], [a^*ba^*(ba^*ba^*)^*], [a^*ba^*ba^*(ba^*ba^*)^*]$. This means the minimal DFA would have three states, and it was given so:

But it seemed to me that the following DFA with two states would achieve the same result (by merging q0 and q2).

This is a contradiction with having three equivalence classes.

What went wrong here, and where?

Your first and third equivalence classes are equivalent to one another. They both contain strings in which there are an even number of $b$s: in the first class, that number is zero; in the third class, it's at least two. For any string in either of those classes, adding a string with an odd number of $b$s gives a string in the language, and adding a string with an even number gives a string not in it.