# Minimal Finite automata that accept binary strings divisible

Minimal Finite automata that accept binary strings divisible by n?

How many minimum states needed in genral for divisibility by n?

some says exactly n states and others <=n ,so what is the correct answer?

I cant understand anything from these documents.

## Responses

here u are asking for binary strings
so num of states will be n if n is odd
if n is even the we have two possiblities
!) if n is pow of 2 say 2^k
then num of states is k+1
example dividible by 2 is 2^1 num of states are 1+1=2

2) if n is not pow of 2 then divide n by 2
a) if on first attempt u get an odd num then num of states will be  (odd num +1)
ex n=10 not in pow of 2 divide it 10/2=5 so we get 5 in frst attempt so 5+1=6 states

b) if we dint get the odd num in frst attempt then divide until we get frst odd num nd then num of states will be (odd num + 2)

ex: n=24 24/2=12 12/2=6 6/2=3 so states will be 3+2=5

bro,but for binary number  divisible by 4 we need 4 states know?

but as per ur strategy only three states ,how can u draw dfa with three states for divisibility by 4?

And also if u have tips like these minimal Dfa's please share with us?