Example

(Thanks to Justin)

This FSA accepts all binary strings N such that N mod 5 = 4.  How does one construct such an FSA?   First note that as a binary string is read left to right, if the next digit read is 0, the result is that the binary string now seen is two times the value of the binary string seen before this digit was read (i.e., reading a 0 is the same as shifting the binary string left one bit, which is the same as multiplying it by 2).  If the next digit read is a 1, the result is that the binary string now seen is two times the value of the binary string seen before this digit was read, plus 1 (i.e., reading a 1 is the same as shifting the binary string left one bit and adding 1).  So, at each step in processing a binary input string, the FSA must keep track of the value of the binary number seen so far mod 5. If the binary number seen so far is N, then the FSA must keep track of whether N mod 5 is 0, 1, 2, 3, or 4 (the FSA must have 5 states). 

How is the next state determined. Here is a hint.  Suppose the FSA is in state r1.  This state remembers that the binary number read so far, N, is such that N mod 5 = 1. That is, N = 5*k + 1 for some k. If a 0  is read next, the binary number now seen is 2*N, or 2*(5*k + 1), or 10*k + 2, which is the same as 5*2*k+2.  Thus, the new state corresponds to (5*2*k+2) mod 5, which is 2. Similarly, if the digit 1 is read next, the binary number seen at this point is 2*N +1.  Since N = 5*k +1 for some k, 2*N+1 is 10*k+2+1 = 5*2*k+3.  Thus the next state corresponds to (5*2*k+3) mod 5, which is 3.