DFA

Question

Number of states in the minimized DFA that accepts all strings over alphabets $\Sigma=\{0,1\}$ in which number of $0's$ is divisible by $8$ or number of $0's$ is divisible by $16$ is _______.

Answer 1

L1 = number of 0's divisible of 8 , we will have 8 states, ( as each state represent modulo-8)

L2= number of 0's divisible of 16, those are divisible of 16 are already divisible of 8, is already present is L1, i.e, L2 is subset of L1.

So L1 U L2 = L1 only 

we will have simple DFA  over {0,1},such that no of 0's are divisible of 8 , having 8 states only 

Comments

For $2^n$ division, we just need to check if last $n$ digits are 0's.

---

That is something else, when question is about binary number interpreted as decimal is divisible by 8, that mean strings ending with 000, here it is about no of 0's only.

---

Sorry.. missed that..