marks$]$ Suppose $=\{0,1\},Q=\{q_1,q_2,q_3\},q_0=q_1$ and $F\frac{O}{?}$ with

$FQ.$ How many possible unique finite automata are there? Use counting

techniques and do not try to list them, as there are just too many.

$[6$ marks$]$ Design $2$ different specific finite automata that could potentially

satisfy restrictions in the previous question. Give them first as state dia$-$

grams. Then give their formal descriptions. If working with others, make

your automata different from theirs.

$[3$ marks$]$ Give examples of $3$ strings of length at least $8$ accepted from

each of your automata from the previous question, and so give $6$ total strings.

$[2$ mark$]$ What are the longest substring$($s$)$ that have repeated instances

in your $3$ strings in the previous question for your last machine?

$[3$ marks$]$ Design a finite automata in the form of a state diagram that

recognizes the language contains at least three $1s.$

$[8$ marks$]($Problem $1\mathrm{.}31,$ p$.88)$ For any language $A,$ let $A^R=\{w^R|winA\}.$

Show that if $A$ is regular, so is $A^R.($Hint: consider Exercise $1\mathrm{.}11,$ pg $85)$