DFA Problem #3

Problem:

Construct dfa that accept strings on {0, 1} if and only if the value of the string,
interpreted as a binary representation of an integer, is zero modulo five. For example,
0101 and 1111, representing the integers 5 and 15, respectively are to be expected.


Solution:
There are two keys to solving this problem: 1) Labelling the states and 2) Knowing how binary arithmetic works. It is absolutely essential that you know what happens to a binary number as its digits are shifted left. If you do not, it is simple... each shift left multiplies the current value by 2. Then, if the new digit is a 1, you add 1. 


Example:
1010₂ = 10₁₀ 


Treating '1010' as a string, the next input can either be a 1 or a 0. Remembering that as the digits are shifted, the value doubled:

10100₂ = 20₁₀ 
and therefore 
10101₂ = 21₁₀ 


So, lets call the original string 'n'. Then shifting n left by one place, the potential values are either
2n 
OR 
2n + 1 


Notice that the same treatment may be applied to the modulus (remainder). 


Now, lets get into the problem. There are 5 potential remainders when dividing by 5 and we can use these remainders as the labels for our nodes: {0,1,2,3,4}. The equation states that the accept state is 0. So, 

The order and layout will be apparent once we start connecting the dots. 

Lets assume starting that we start with an empty string... obviously, the first input will either be a 1 or a 0 and therefore the modulus will either be a 1 or a 0. So, it is safe to have node 'q0' be the initial state as well as the final state. After this has been figured out, it is simple to connect the dots! All that needs to be done is to apply the binary shift arithmetic to each modulus indicated at the node. Two lines will be drawn from each node, a 1 or a 0 (obviously) which correspond to the equations 2n + 1 and 2n respectively, where n is the modulus at the given state. 

First, lets do all of the 0s. 

d(q0,0) = q0

d(q1,0) = q2 

d(q2,0) = q4

d(q3,0) = q1

d(q4,0) = q3

In case you didn't follow, take the number next to the 'q' on the left side of the equation, multiply it by 2, and then divide the result by 5. Take the remainder, and that is the node it should be connected to. 

Now lets do the same for an input of 1 at each node. Same process of before, but instead of just multiplying by 2, we also add 1 before dividing by 5. 

d(q0,1) = q1

d(q1,1) = q3

d(q2,1) = q0

d(q3,1) = q2

d(q4,1) = q4

Once those lines are inserted, the solution is complete! If you did not follow this, review binary multiplication a couple of times and it should become clear.