(a) Give a recursive definition of the function zeros(s), which counts the number of zeros in a bit string s {0, 1} .

Hint: the domain of this function is {0, 1} and its codomain is the set of nonnegative integers N. For example, zeros(1101) = 1 and zeros(0010) = 3.

(b) Use structural induction to prove that zeros(st) = zeros(s) + zeros(t). Your proof will need to use the definition you came up with in part (a). Note that st refers to the concatenation of the strings s and t; on the RHS the + is addition of integers.

Hint: you may find the recursive definition of string concatenation