1
$\begingroup$

What is the minimal number of DFA states required to recognize binary numbers (encoded MSB to LSB) which are divisible by 6 and 8?

For divisibility by $6$ we required $6$ states.

For divisibility by $8$ we require $4$ states.

So in total, we need $6 \times 4$ states = $24$ states.

Am I correct? Can we do it with fewer states?

|cite|improve this question
$\endgroup$
  • $\begingroup$ What do you mean by "decimal equivalent"? Is the binary number encoded MSB first or LSB first? $\endgroup$ – Yuval Filmus Nov 11 '17 at 14:57
  • $\begingroup$ By decimal equivalent I mean that it's not the word length of binary string but the actual value like 1000 is 8 and not 4. $\endgroup$ – Rajesh R Nov 11 '17 at 15:15
  • $\begingroup$ So this is MSB first. $\endgroup$ – Yuval Filmus Nov 11 '17 at 15:16
1
$\begingroup$

In order to obtain an upper bound on the number of DFA states required to recognize some language, the simplest method is to give a DFA with that (or lower) number of states. In order to obtain a lower bound on the same number, the easiest route is to give $m$ pairwise indistinguishable words. These are $m$ words $x_1,\ldots,x_m$ such that for each $i \neq j$ there exists a word $y$ such that $x_i y \in L$ whereas $x_j y \notin L$, or vice versa. This set of words shows that every DFA for $L$ must contain at least $m$ states (why?).

In your case, the minimal number of states is much smaller than 24, though the exact number depends on the encoding. Instead of solving your question, let me calculate the minimal number of states in a DFA accepting all (non-empty) decimal numbers (encoded MSB to LSB) which are divisible by 6. I claim that this number is 4. For the upper bound, consider a DFA with states $q_0,q_1,q_2,q_A$, where $q_0$ is the initial state and $q_A$ is the accepting states. The transition table of the DFA is $$ \begin{array}{c|ccccccccccc} \delta & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\hline q_0 & q_A & q_1 & q_2 & q_0 & q_1 & q_2 & q_A & q_1 & q_2 & q_0 \\ q_1 & q_1 & q_2 & q_A & q_1 & q_2 & q_0 & q_1 & q_2 & q_A & q_1 \\ q_2 & q_2 & q_0 & q_1 & q_2 & q_A & q_1 & q_2 & q_0 & q_1 & q_2 \\ q_A & q_A & q_1 & q_2 & q_0 & q_1 & q_2 & q_A & q_1 & q_2 & q_0 \\ \end{array} $$

You can show by induction that upon reading a word $w$:

  • If $w = \epsilon$ or $w \equiv 3 \pmod{6}$, the machine is in state $q_0$.
  • If $w \neq \epsilon$ and $w \equiv 1,4 \pmod{6}$, the machine is in state $q_1$.
  • If $w \neq \epsilon$ and $w \equiv 2,5 \pmod{6}$, the machine is in state $q_2$.
  • If $w \neq \epsilon$ and $w \equiv 0 \pmod{6}$, the machine is in state $q_A$.

This easily implies that this DFA accepts our language.

For the lower bounds, we use the set of words $\{0,1,2,3\}$. The following table gives the words $y$ separating each pair of words: $$ \begin{array}{c|cccc} y & 0 & 1 & 2 & 3 \\\hline 0 & & \epsilon & \epsilon & \epsilon \\ 1 & \epsilon & & 2 & 0 \\ 2 & \epsilon & 2 & & 0 \\ 3 & \epsilon & 0 & 0 & \end{array} $$ (These correspond to the states $q_A,q_1,q_2,q_0$.)

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Sir, how are you considering input as 2,3,4,5 etc. It should be only 0's and 1's as it's binary right? $\endgroup$ – Rajesh R Nov 11 '17 at 15:45
  • $\begingroup$ Let me quote myself: "Instead of solving your question, let me calculate the minimal number of states in a DFA accepting all (non-empty) decimal numbers (encoded MSB to LSB) which are divisible by 6." $\endgroup$ – Yuval Filmus Nov 11 '17 at 15:46
  • $\begingroup$ I understood that your DFA accepts numbers divisible by 6 . But how did you construct it ? What do the states q0,q1,q2 mean ? $\endgroup$ – Rajesh R Nov 11 '17 at 16:26
  • $\begingroup$ That's explained by the four bullets. They correspond to residues mod 6. $\endgroup$ – Yuval Filmus Nov 11 '17 at 16:33
  • $\begingroup$ Till know I used to think that for all remainders we have separate states. Like for divisibility by 6, 6 states for remainders 0-5. How did you club remainder 1 and 4. Is it any divisibility trick? $\endgroup$ – Rajesh R Nov 11 '17 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.