DFA based division

Example

Suppose we want to check whether a given number ‘num’ is divisible by 3 or not

1. When we are at state 0 and read 0, we remain at state 0.
2. When we are at state 0 and read 1, we move to state 1, The number so formed(1) in decimal gives remainder 1.
3. When we are at state 1 and read 0, we move to state 2, The number so formed(10) in decimal gives remainder 2.
4. When we are at state 1 and read 1, we move to state 0, The number so formed(11) in decimal gives remainder 0.
5. When we are at state 2 and read 0, we move to state 1, The number so formed(100) in decimal gives remainder 1.
6. When we are at state 2 and read 1, we remain at state 2, The number so formed(101) in decimal gives remainder 2.

The transition table looks like following:

state   0   1
_____________
0      0   1
1      2   0
2      1   2

Let us check whether 6 is divisible by 3?
Binary representation of 6 is 110
state = 0
1. state=0, we read 1, new state=1
2. state=1, we read 1, new state=0
3. state=0, we read 0, new state=0
Since the final state is 0, the number is divisible by 3.

Let us take another example number as 4
state=0
1. state=0, we read 1, new state=1
2. state=1, we read 0, new state=2
3. state=2, we read 0, new state=1
Since, the final state is not 0, the number is not divisible by 3. The remainder is 1.

Note that the final state gives the remainder.