DFA minimisation

Question

Why no of states in a dfa(language having binary strings whose integer equivalent is divisible by n) where n = 8,12.., are different form a standard dfa where we say that no of states will be n-1(for n =2,3,5)?

Comments

For Decimal ( Binary String ) = 0 mod n

  i)   If n = $2^m$, then No.of states in Minimal DFA = m + 1 (Proof given by arjun sir in this question)

 ii)   If  n = odd, then No.of states in Minimal DFA = n

iii)   If n = even but not power of 2, then follow division technique until your value matched with case i or  case ii

For example,

If n=21 ===> then No.of states in Minimal DFA = 21

If n=32 ===> then No.of states in Minimal DFA = 6

If n=22 ===> then No.of states in Minimal DFA = 12 due to

( $\frac{22}{2}$→ one time division → 11 → is odd ) ===> 1+ 11

If n=12 ===> then No.of states in Minimal DFA = 5 due to

( $\frac{12}{2}$ → $\frac{6}{2}$ → two time division → 3  →  is odd )

===> 2 + 3

Source: https://gateoverflow.in/272643/cant-understand-the-intution-behind-the-shortcut

Answer 1

Remember this trick : while solving binary strings divisibility problem when interpreted as decimal number.

Divisor is d

 

If d is odd then d states are needed. i.e divisible by 3,5,7 will have 3,5,7 states

If  di even then divide it by two till you get a odd number(say x). So No. of states = x + number_of_times_divided_by_2

Eg:

12 --> (12/2),(6/2),3 (stop odd number has come) = 3+1+1 =5 sates

18 -->(18/2),9  = 9+1 = 10 states

Comments

Any proof, reason for this trick??