Divisibility checking with Finite states
09 Mar 2009 Leave a Comment
in Computers and Internet Tags: Computers, FAFL, Mathematics
I found a really interesting problem in the book titled “Introduction to Automata Theory, Languages, and Computation” by John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman. The problem is to check whether a given binary number is divisible by 5 or not.
The trick to solve this problem is observation. After inputting a series of bits, the last bit that can be entered may be a 0 or a 1. If it is a zero, the number just gets doubled. If its is a 1, the number is doubled and 1 is added to it. Let the number inputted previously be 5a+b. where b is the remainder. If the last bit is entered, say 0, the number becomes 10a + 2b. If you divide this number by 5, the remainder is 2b mod 5, which rangers from 0 to 4. So, you need 5 states to represent each remainder from 0 to 4. The following shows the transition table.
| δ | 0 | 1 |
|---|---|---|
| → * q0 | q0 | q1 |
| q1 | q2 | q3 |
| q2 | q4 | q0 |
| q3 | q1 | q2 |
| q4 | q3 | q4 |
The transition table is very easy to obtain by just mapping the remainders onto their respective states. One advantage with this approach is that one can extend this process to test divisibility to any number. Especially prime numbers as the number of states required to test divisibility exactly corresponds to N, the number with which divisibility is to be tested.
