Question

No. of states in the minimal finite automata which accepts the binary strings whose equivalent is divisible by 32 is ________?

A. 5

B. 6

C 31

D 32

Comments

When It is a mod n problem it contains n states, 0 to n-1 as remainders. So mod 32 means 32 states 0 to 31 as remainders. Its a mod n problem so ANS 32

Answer 1

The answer is 6. 

For binary strings divisible by 2 we check if the last char from the right is a 0. 

For binary strings divisible by 2² we check if the last char from the right is a 00.

...

For binary strings divisible by 2⁵ we check if the last char from right is a 00000

So, we need 6 states for counting the number of 0's to right, from 0 to 5. And there is no non-determinism required and we are thus getting a minimal state DFA. 

Comments

@Arjun

Beautiful Explanation.

---

I think such technique work for binary string whose equivalent is divisible by a number of form 2^k.

But if it is some random number like 7(divisible by 7)then we will have 7 states i think.Is it correct?Can anyone reply?

---

very nice , thanks

Answer 2

Hope this helps

Answer 3

answere is D

each remainder contributing to one state

Answer 4

When It is a mod n problem it contains n states, 0 to n-1 as remainders. So mod 32 means 32 states 0 to 31 as remainders. Its a mod n problem so ANS 32