# For a binary string x = a0a1&nbsp;· · · an−1&n...

For a binary string x = a0a1 · · · an−1 define val(x) to be the value of x interpreted as a binary number, where a0 is the most significant bit. More formally, val(x) is given by
How many minimum states will be in a finite automaton that accepts exactly the set of binary strings x such that val(x) is divisible by either 4 or 5.

## Responses

For n a natural number, let Ln = {x ∈ {0, 1}* | val(x) is divisible by n}. Observe the following.
(i) For a binary string x, x ∈ Ln iff val(x) mod n = 0.
(ii) if val(x) = i mod n for a binary string x, then val(xb) ≡ (2i + b) mod n, for b = 0, 1.
So to construct a DFA for Ln, it suffices to take n states q0, . . . , qn−1, with qi recording the fact that the value of the string read so far is i mod n. Under this interpretation, q0 will be the initial and (only) final state, and the automaton will transition from state qi to qj on reading letter b ∈ {0, 1}, where j = (2i + b) mod n.

For example, the automaton for L5 is given in the figure. The reader can construct the automaton for L4 in a similar manner. Or one could observe that L4 = {0, 1}*{00} and construct a simpler automaton.
Finally, the language in question is L4 ∪ L5, for which one can appeal to the closure of regular languages under union (and provide the appropriate NFA).