CMI2013-B-01

Question

For a binary string $x = a_0a_1 \dots a_{n−1}$ define $val(x)$ to be the value of $x$ interpreted as a binary number, where $a_0$ is the most significant bit. More formally, $val(x)$ is given by

$\Sigma_{0 \leq i < n} 2^{n-1-i} .a_i$
Design a finite automaton that accepts exactly the set of binary strings $x$ such that $val(x)$ is divisible by either 4 or 5.

Answer 1

an is basically the decimal representation of the binary number, so a total of 20 states will suffice to construct the DFA

Answer 2