The procedure can be explained as follows: Scan the list of numbers and keep looking for the remainder of the string when divided by 3.
There are three cases (and states):
- When the remainder is zero: When we are in this state, no matter how many zeros we add, we will get a remainder of zero. If we add a 1, then the remainder is 1 and it goes to state 1
- When the remainder is one: If we add 1, then it is equivalent to multiplying the number by 2 and adding one – which means if we had x that had remainder 1, then now we have (2x+1)%3, which is equivalent to 3%3, which is zero. Hence it goes to state 1. When we add 0, then we multiply the number by 2, whence the remainder becomes 2 and it goes to state 2.
- When the remainder is two: If we add 0 to it, then we are multiplying the number by 2. When x%3 is 2, by simple arithmetic we can find that (2x)%3 is 1, so it goes to state 1. If we add 1 to it, then (2x+1)%3 is 2 only (again by simple arithmetic) in which case it remains in state 2.
Using this reasoning, we can construct a DFA to check for divisibility by any number.