The Gateway to Computer Science Excellence
496 views

Lets first prove the number of states in the minimal DFA for accepting binary strings divisible by a given number say $12$

We need $3$ states for checking if a binary number is divisible by $3$ - each state corresponding to remainders $0,1,2.$ Here, remainder $0$ will be the final state for divisibility by $3$. If we add a '0' transition from this state to another state and make it FINAL, we get divisibility by $6$ as a '0' at end ensure number is divisible by $2$ and also retains the property that the number is divisible by $3$ which makes it divisible by $6.$ Add one more state like this and we get numbers divisible by $3\times 2\times 2 = 12.$ Thus we need $5$ states in the minimal DFA for divisibility by $12.$


The above construction works because in the DFA for divisibility by $3$, there will be no outgoing edge on $0$ to the final state from any other state. This is because no number not divisible by $3,$ when multiplied by $2$ will become divisible by $3$ (holds for any odd number). But there will be self edge on the final state for '0' - when we add the new state for divisibility by $6,$ we remove this edge and make it go to the new FINAL state. 


The above construction works in general too. To check if a binary number is divisible by $n$

  1. If $n$ is a power of $2$ we need $\log_2 n+1$ states in the minimal DFA 
  2. If $n = 2^k \times m,$ where $m$ is odd, then we need $k + m$ states in the minimal DFA

PS: To be proved: To check a binary number for divisibility by any odd number $k$ requires $k$ states in the minimal DFA.


To find the minimal number of states in the DFA accepting binary strings divisible by $m$ and $n:$

Here, we have to check divisibility by $m$ and divisibility by $n$. So, we can take this as divisibility by $\text{LCM}(m,n).$


To find the minimal number of states in the DFA accepting binary strings divisible by $m$ or $n:$

posted Sep 20 in Theory of Computation by Veteran (425,085 points) | 496 views
19
Like
8
Love
1
Haha
0
Wow
0
Angry
0
Sad

2 Comments

Thanks for this post.
Amazing work Sir
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,564 answers
195,746 comments
101,694 users