Exercise 1.9 Given that binary number strings are read with the most significant bit first and may have leading zeroes, construct DFAs for each of the following languages:

a) Binary number strings that represent numbers that are multiples of 4, e.g., 0, 100 and 10100.

b) Binary number strings that represent numbers that are multiples of 5, e.g., 0, 101, 10100 and 11001. Hint: Make a state for each possible remainder after division by 5 and then add a state to avoid accepting the empty string.

c) Given a number n, what is the minimal number of states needed in a DFA that recognises binary numbers that are multiples of n? Hint: write n as a2 b , where a is odd.