Question

Design a finite state machine that accepts binary strings divisible by 5. Input is fed to the FSM one bit at a time, from the most significant bit to the least significant bit (left to right). For example, 1010 should be accepted, but 1100 should be rejected. Clearly explain how you designed your state transitions. Showing the FSM alone is worth minimal credit!

Answer 1

We want to design a finite state machine that accepts binary string which is divisible by 5.We know that every natural numbers can be represented as,

5m(remainder 0 when divide by 5)

5m+1(remainder 1 when divide by 5)

5m+2(remainder 2 when divide by 2)

5m+3(remainder 3 when divide by 5)

5m+4(remainder 4 when divide by 5).

In our FSM we use these variables as 5 states.

To design the FSM, we also know that every binary numbers will become double if left shift them and add 0 to the first position.

For example, 10 represents 2

If we left shift 10 and add 0 to its first position, it will become 100=4(double of 2)

Also we know, if we add 1 at the first position after left shifting the binary number, the result will be double+1.

For example, 10 represents 2

If we left shift and add 1 to its first position, it will become 101=5(double of 2+1)

This concept is used to implement the FSM.

Let, 5m be the initial state, if we double it, it become 10 and it is divisible by 5.Which means in state 5m, if we give 0, it will retain in the same state.

Similarly, if we double and add 1to it, it will become 10m+1(remainder 1, when divide by 5) which means when 1 is given to 5m it will go to the state 5m+1.

All the other state can apply the same concept which is applied to state 5m.Then we will get the FSM that accept the binary string which is divisible by 5.The final FSM is shown below,