$($c$)$ Using the following theorem:

A positive integer $($including $0)$ is divisible by $3$ if and only if the sum of its digits is a

multiple of $3.$ For example, the number $732$ is divisible by $3$ since $7+3+2=12$ is a

multiple of $3.$ The number $143$ is not divisible by $3$ since $1+4+3=8$ is not a multiple of

Suppose we design a machine that recognizes the numbers that are divisible by $3.$ We

call the machine $M_3$

i$.(3$ points$)$ Draw the state diagram of a DFA $M_3$ with alphabet $=\{0,1,2,3,4,5,6,7,8,9\}$

and

$L(M_3)=\{xin{}^{**}|x=3k,$kin$u\{0\}\}$

HINT: Use the states of your DFA to keep track of $n$ mod $3.$ Clearly show accepting

states.

ii$.(3$ points$)$ Trace the computation of your machine on input $76521.$ Does your machine

accept $76521?$