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.

http://www.mathematica-journal.com/data/uploads/2011/01/Sutner.pdf

Responses

shreyans's picture

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

maheshkumars's picture

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?

Did not found what you are looking for, Ask your doubt or Help by your contribution

Enter your search keyword:

Search form

Wait!

Here is a chance to join biggest community of technical Students,
Tutors with FREE learning resources and so much more.
It takes less then 60 seconds.