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 | 496 views
19
Like
8
Love
1
Haha
0
Wow
0
Angry
0