$($V$)$ Use the construction in Theorem $3\mathrm{.}1$ and find an NFA recognizing the languages

$($i$)(01+001+010{)}^{*}$

$($VI$)$ Convert the NFA constructed above for $(01+001+010{)}^{*}$ to an equivalent DFA

THEOREM $3\mathrm{.}1$

Let $r$ be a regular expression. Then there exists some nondeterministic

finite accepter that accepts $L(r).$ Consequently, $L(r)$ is a regular

language.

Proof: We begin with automata that accept the languages for the simple

regular expressions $\frac{O}{,},$ and ain$.$ These are shown in Figure $3\mathrm{.}1($a$),$

$($b$),$ and $($c$),$ respectively. Assume now that we have automata $M(r_1)$ and

$M(r_2)$ that accept languages denoted by regular expressions $r_1$ and $r_2,$

respectively. We need not explicitly construct these automata, but may

represent them schematically, as in Figure $3\mathrm{.}2.$ In this scheme, the graph

vertex at the left represents the initial state, the one on the right the final

state. In Exercise $7,$ Section $2\mathrm{.}3,$ we claim that for every nfa there is an

equivalent one with a single final state, so we lose nothing in assuming

that there is only one final state. With $M(r_1)$ and $M(r_2)$ represented in

this way, we then construct automata for the regular expressions $r_1+r_2,$