let the ∑ = {0,1} ===> strings possible are should be Binary strings.
No.of States in Minimal DFA that accepts, Decimal( Binary String ) = 0 mod n
in ACE coaching institute, i learned that
For Decimal( Binary String ) = 0 mod n
i) if n = 2$^m$ then No.of states in Minimal DFA = m + 1
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
But i didn’t know how it is prove it, i mean what is the logic behind that ?
what is the answer for following questions ?
Decimal( Binary String ) = 0 mod x or 0 mod y
- neither x divides y nor y divides x
- either x is divides y or y divides x