I have found in a book the example of how to make a FA that accepts those numbers that are divisible by 3, that means that n mod 3=0. In the example the author used the binary representation of the number to be evaluated. The resulting automata is:
The states represent the probable remainders, that could be 0, 1 or 2. Some additional explanation is in the following part:
I have tried the following examples to test this automata:
- If I try to do 6 mod 3 that will result in 0, so I will go from the initial state (upper part of the figure) to the acceptance state, that is because the modulus is 0.
- If I try 5 mod 3 or 101 mod 11 that would be 2, which in binary is 10. If I want to apply again 2 mod 3. I will end up again with 2 and not reaching an acceptance state. From the upper part I followed the path 1--state 1--0--state 2. What happens there? it just stays in that state 2?
I just do not have a clear picture of how to test this FA for example with an input of 81 mod 3, does it make partial divisions? When I try to follow it I end up in an acceptance state even before finishing to evaluate the remainder.