Carry out the algorithm presented to get the minimal DFA equivalent to the

twelve$-$state DFA drawn below. This DFA has alphabet $\{0,1\}$ and determines whether a string rep$-$

resents a number in binary that is divisible by twelve. The state set is $\{0,1,2,3,4,5,6,7,8,9,10,11\}.$

On input $0,$ the machine goes from state i to state $2$i$\%12.$ On input $1,$ the machine goes from state

i to state $(2$i $+1)\%12.$

$0123$

$4567$

$891011$

$0$

$10$

$1$

$0$

$1$

$1$

$0$

$0$

$10$

$1$

$1$

$0$

$1$

$0$

$0$

$1$

$0$

$1$

$1$

$0$

$0$

$1$

Give each of the equivalence relations produced by the algorithm and demonstrate that your last

one is really the last one. Draw the resulting minimal DFA.

$1$