CODEWITHSUNDEEP
dfa
Chloe_1993
Chloe_1993

Reputation: 15

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

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?

My DFA

Upvotes: 1

Views: 1704

Answers (1)

John Kugelman
John Kugelman

Reputation: 361595

It looks correct to me.

You could make two simplifications:

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

  2. q1 and q3 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.

Upvotes: 1

Related Questions