DFA for binary numbers that have a remainder of 1 when divided by 3

Question

I need a DFA for a set of all strings beginning with a 1 that, interpreted as the binary representation of an integer, have a remainder of 1 when divided by 3.

For example, the binary number 1010 b is decimal 10. When you divide 10 by 3 you get a remainder of 1, so 1010 is in the language. However, the binary number 1111 b is decimal 15. When you divide 15 by 3 you get a remainder of 0, so 1111 is not in the language.

I've attached my DFA below. Could you please check it?

Answer 1

It looks correct to me.

You could make two simplifications:

1. q₄ represents (mod 0), so you could make it the starting state and get rid of q₀ and q₅. (Unless you are required to reject strings beginning with a 0? Your question doesn't specify.)

2. q₁ and q₃ can be merged. They both represent (mod 1) and have the same transitions.

These two changes would leave you with exactly 3 states, one for each remainder.