Minimize the size of the state set by computing the state equivalence relations.

Hint: The minimized machine must have four states. $($Name it Machine M$2)$

e$)$ Change one non$-$final state in the original eight$-$state machine $($Machine M$1)$

into a final state. $($Name it Machine M$3)$

f$)$ What is the regular expression for the language accepted by Machine M$3?$

g$)$ Redo the minimization in $($e$).($Name it Machine M$4)$

h$)$ How large could the new state set be$?$ How small could it be$?($Machine M$4)$

i$)$ Justify your answer.

$2.$ Construct finite$-$state automata that recognize the following regular expressions.

a$)0*(01)*$

b$)(01$V$111)*10*(0$V$1)$

c$)(001$V$(11)*)*$