For each of the state diagrams in Exercise $5\mathrm{.}40,$ use Algorithm $6\mathrm{.}2\mathrm{.}2$ to construct a regular expression for the language accepted by the automaton.

a$)$

b$)$

c$)$

d$)$

Algorithm $6\mathrm{.}2\mathrm{.}2$

Construction of a Regular Expression from a Finite Automaton

input: state diagram $G$ of a finite automaton with one accepting state

Let $q_0$ be the start state and $q_t$ the accepting state of $G.$

repeat

$1\mathrm{.}1.$ choose a node $q_i$ that is neither $q_0$ nor $q_t$

$1\mathrm{.}2.$ delete the node $q_i$ from $G$ according to the following procedure:

$1\mathrm{.}2\mathrm{.}1$ for every $j,k$ not equal to $i($this includes $j=k)$ do

i$)$ if $w_{j,i}\frac{O}{,}{w}_{i,k}\frac{O}{?}$ and $w_{i,i}=\frac{O}{?},$ then add an arc from node $j$ to node $k$ labeled $w_{j,i}{w}_{i,k}$

ii$)$ if $w_{j,i}\frac{O}{,}{w}_{i,k}\frac{O}{?}$ and $w_{i,i}\frac{O}{?},$ then add an arc from node $q_j$ to node $q_k$ labeled $w_{j,i}(w_{i,i}{)}^{**}{w}_{i,k}$

iii$)$ if nodes $q_j$ and $q_k$ have arcs labeled $w_1,w_2,$dots,$w_s$ connecting them, then replace the arcs by a single arc labeled $w_1{w}_2$cdots$w_s$

$1\mathrm{.}2\mathrm{.}2$ remove the node $q_i$ and all arcs incident to it in $G$

until the only nodes in $G$ are $q_0$ and $q_t$

determine the expression accepted by G