a$.[12$ pts$]$ For the state machine shown below $,$ which of the following expressions will result in a match? $($The process starts at state $1$ and can end in either state $3$ or $5.)$

Choose from the following:

de

abcd

abc$*|$d$+$k

dec

abc

ddee

$$b$.[8$ pts$]$ List $4$ additional valid expressions $($not listed above$)$ for the state machine shown in the figures! E$.$g$.,$ abcc is a valid expression. $($Matching up to $6$ letters is sufficient!$)$

$$c$.[8$ pts$]$ Create a state machine $($similar to the one shown in Figure $1)$ that matches the regular expression ab$*$a and a second one that matches the regular expression $($a$|$b$)$c$$

$$d$.[7$ pts$]$ Write the implementation for the class Edge that represents an edge in a finite state machine.

class Edge:$$

$$ def $\_\_$init$\_\_($self$,$ c$,$ dest$)$:

$$e$.[15$ pts$]$ Complete the missing lines in the code for the class Vertex that represents a vertex in a finite state machine.

$$

class Vertex:

$$ def $\_\_$init$\_\_($self$,$ n$)$:

$$ self.number $=$ n

$$ self.edgeList $=[]$

$$ self.isAcceptingState $=...$

$$ def setAcceptingState$($self$)$:

$...$

$$ def addEdge$($self$,$e$)$:

$...$

$$ def followEdge$($self$,$c$)$:

$...$