How many equivalence classes in the RL relation for {w in {a, b}* | (#a(w) mod m) = ((#b(w)+1) mod m)}

Question

How many equivalence classes in the RL relation for

{w in {a, b}* | (#a(w) mod m) = ((#b(w)+1) mod m)}

I am looking at a past test question which gives me the options

• m(m+1)
• 2m
• m^2
• m^2+1
• infinite

However, i claim that its m, and I came up with an automaton that I believe accepts this language which contains 3 states (for m=3).

Am I right?

Answer 1

Actually you're right. To see this, observe that the difference of #a(w) and #b(w), #a(w) - #b(w) modulo m, is all that matters; and there are only m possible values of this difference modulo m. So, m states are always sufficient to accept a language of this form: simply make the state corresponding to the appropriate difference the accepting state.

In your DFA, a2 corresponds to a difference of zero, a1 to a difference of one and a3 to a difference of two.