First let me define what is “Divisibility language”.
We have two very similar looking type of languages. I call one type “Length divisibility language” and other I call “Divisibility language”
"Length divisibility machines/languages" are different from "divisibility languages".
Let me define what I mean by “Length divisibility language” and by “Divisibility language” :
Length divisibility language : Given binary string w, we ask questions like :
(length of w) mod n = r, Or
(#0 in w) mod n = r, Or
(#1 in w) mod n,
etc.
Divisibility language : Given binary string, we ask Question :
(Decimal value of that binary string) mod n = r
So first we should Note this difference between the two types of languages or problems.
For Length divisibility, we have the result that minimal DFA will have n states(regardless of r), for Length divisibility by n problem. But for divisibility languages, this might not be true. Yes, we can say that for divisibility language, minimal DFA will have at most n states.
Result 1 : For Length divisibility by n languages, as described above, the number of states in minimal DFA will be ALWAYS n.
Result 2 : For divisibility language, binary string divisible by n, when r = 0
i.e. (Decimal value of that binary string) mod n = 0
we have the following results :
(a) : In binary numbers, if the divisor is a power of 2 (i.e. n = $2^k$) then the minimum number of states required will be $k+1$.
How would you design such an automaton? Just see the properties of binary numbers. For a number, say 8 (which is $2^3$), all its multiples will have the last 3 bits as 0. For example, 40 in binary is 101000. Therefore for a language to accept any number divisible by 8 we just need an automaton which sees if the last 3 bits are 0, which we can do in just 4 states instead of 8 states. (In fact, this can be extended to any base. For a ternary base number system, if for example we need to design an automaton for divisibility with 9, we just need to see if the last 2 numbers of the input are 0. Which can again be done in just 3 states.)
(b) : If the divisor isn't power of 2 :
In a binary system, for example, if we take the divisors of 3 then 3 states in mDFA,
For any odd number n in a binary system, we need n states in minimal DFA to define the language which accepts all multiples of n.
On the other hand, if the number is even but not a power of 2 (only in case of binary numbers) then we need to divide the number by 2 till we get an odd number and then we can find the minimum number of states by adding the odd number produced and the number of times we divided by 2.
For example, if we need to find the minimum number of states of a DFA which accepts all binary numbers divisible by 20, we do :
20/2 = 10
10/2 = 5
Hence our answer is 5 + 1 + 1 = 7. (The 1 + 1 because we divided the number 20 twice).
Exercise Question : L = { $w | w \in \{ 0,1 \}^* , w \text{ is multiple of 6 and 8} $ }
Answer : Binary number divisible by 6 and 8, then we know that a number is divisbile by 6 and 8 if and only if it is divisible by 24 (LCM(6,8) = 24), so, finding the number of states in mDFA for the language "binary number divisible by 6 and 8" is same as finding the number of states in mDFA for the language "binary number divisible by 24".
Now, coming to finding the number of states in mDFA for the language "binary number divisible by 24", Note that 24 is neither an odd number, nor a power of 2, So, we apply the following procedure :
if the number is even but not a power of 2 (only in case of binary numbers) then we need to divide the number by 2 till we get an odd number and then we can find the minimum number of states by adding the odd number produced and the number of times we divided by 2.
We need to find the minimum number of states of a DFA which accepts all binary numbers divisible by 24, we do :
24/2 = 12
12/2 = 6
6/2 = 3
Hence our answer is 3 + 1 + 1 + 1 = 6. (The 1 + 1 + 1 because we divided the number 24 thrice).
So, answer will be 6, Not 48 or 16.
NOTE : Note that This divisibility language formulas assume that Empty string is divisible by n.
PROOF of ALL the above claims :
Refer the following brilliant post by Arjun sir for proof of few of the above claims.
https://gateoverflow.in/blog/8651/minimum-number-states-dfa-accepting-binary-number-divisible
I will prove here that :
For any odd number n in a binary system, we need n states in minimal DFA to define the language which accepts all multiples of n.
Objective : To check a binary number for divisibility by any odd number k requires k states in the minimal DFA.
Note that any binary number $abcd = (ab)2^2 + cd; abc = (ab)2^1 + c$
In general, $a_na_{n-1}\dots a_1 = (a_na_{n-1 \dots a_{x+1}})2^x + (a_xa_{x-1} \dots a_1)$
Theorem 1 : If a divides pq and is relatively prime to p then it divides q.
http://www.math.ubc.ca/~cass/courses/m446-03/divisibility.pdf
Proof :
Statement : Language of binary numbers divisible by any odd number n requires n states in the minimal DFA.
The way to prove such results is to twofold: first we prove an upper bound by constructing a DFA accepting the given language(that is n), then we prove a lower bound using Myhill–Nerode theory.
Now I'll prove, by Myhill Nerode Theorem that if n is odd number then All the numbers from 0 to n-1 will be mutually distinguishable.
Note that 0 is already distinguishable from 1 to $n-1$. So, we only need to show that All the numbers from 1 to n-1 will be mutually distinguishable.
By Myhill nerode theorem, two strings u and v are distinguishable if and only if there is some string w such that exactly one of uw, vw belongs to our language.
Take any string $u$ whose decimal value is $a ; 1 \leq a \leq n-1$ , We will add append some string $v$ to $u$ such that uv belongs to our language i.e. $decimal(uv)$ is multiple of $n$. Let $decimal(v) = m$ and let $|v| = i$
So, $a(2^i) + m = n(X)$
Now, take any $b; 1 \leq a < b \leq n-1$ different from $a$ i.e. $a \neq b$
$m = n(X) - a(2^i)$
We will show that for ALL $i \geq 1$, $b(2^i) + m $ is Not multiple of $n.$
Let's check $b(2^i) + m $
= $b(2^i) + n(X) - a(2^i)$ = $2^i(b-a) + n(X)$
$2^i(b-a) + n(X)$ is Not divisible by n. Because $2^i(b-a)$ is Not divisible by n due to the Theorem 1 (NOTE that $1 \leq b-a \leq n-1$ and $i \geq 1$, )
So, this proves that If you take any Two binary strings $u,v$ whose decimal value is between 1 and n-1 and $decimal(u) \neq decimal(v)$ then for ALL strings $w \neq \epsilon$ if $uw \in L$ then $vw \notin L.$
This shows that every number from 0 to $n-1$ is mutually distinguishable.
Useful relevant links :
https://stackoverflow.com/questions/21897554/design-dfa-accepting-binary-strings-divisible-by-a-number-n/22282792
https://www.sciencedirect.com/science/article/pii/S0022000004000200/pdf?md5=d6888310e29849b6406cee916342ef9a&pid=1-s2.0-S0022000004000200-main.pdf
https://cs.stackexchange.com/questions/85850/minimum-number-of-states-in-dfa-accepting-binary-number-with-decimal-equivalent
