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:

3-state DFA

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

2-state DFA

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.


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.