Design a DFA corresponding to the classical paper-scissors-stone game. The alphabet consists of three symbols, say (a, b, c) for paper, scissors and stone, respectively, and each game is a sequence of pairs x_1y_1x_2y_2x_3y_3... where (x_i, y_i) denote the choice of player 1 and 2 at round i. The game ends once x_i notequalto y_i (remaining moves can be ignored). a) How many states are needed? _____ (answer, e.g., 17) b) If players choose their moves independently and uniformly in random (i.e., each symbol with probability of 1/3), what is the mean number of transitions before the game ends? _____ (answer, e.g., 17)