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.


sumitverma's picture

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).

Did not found what you are looking for, Ask your doubt or Help by your contribution

Enter your search keyword:

Search form


Here is a chance to join biggest community of technical Students,
Tutors with FREE learning resources and so much more.
It takes less then 60 seconds.