For each part below, explain how you would construct a finite automaton M satisfying the given description; you do NOT have to actually give an explicit description of the automaton! The main point here is to convince yourself (and the reader) that such an automaton exists.

(a) The language accepted by M is the set of all binary strings s such that, viewed as an integer, s is divisible by n, where n is a specified odd integer. That is, given an odd integer n, we want L(M) = {s {0, 1} | is divisible by n}.

(b) M processes input where each input symbol represents a move in a game of tic-tac-toe. In case an illegal move is input, M does not change its state. At the end of processing an input string, M will be in state X if player X has won; in state O if player O has won; in state T if the game has ended in a tie; and these three states are the only accept states.