Every regular expression has an equivalent epsilon-NFA

We construct $N_R$ by induction on the structure of $R$, maintaining one designated start state and one designated accepting state, with that designated state as the entire accepting set. For the base expressions, use: a two-state gadget with no transition to its accepting state for $\mathrm{\varnothing }$; a two-state gadget joined by one $\epsilon$-edge for $\epsilon$; and a two-state gadget with one $a$-edge for a letter $a\in \mathrm{\Sigma }$.

For $R+S$, add a fresh start state with $\epsilon$-edges to the starts of the machines for $R$ and $S$, and a fresh accepting state reached by $\epsilon$-edges from their old accepting states; only the fresh state is accepting. For $RS$, connect the accepting state of the machine for $R$ to the start state of the machine for $S$ by an $\epsilon$-edge, make the former nonaccepting, and retain only the accepting state of the machine for $S$. For $R^{\ast }$, add fresh start and accepting states, an $\epsilon$-edge from the new start to the new accept, an $\epsilon$-edge from the new start into the old start, and $\epsilon$-edges from the old accept both back to the old start and to the new accept; only the new accept is accepting.

The base gadgets recognize exactly $\mathrm{\varnothing }$, $\{\epsilon \}$, and $\{a\}$. By [L3], the union gadget accepts exactly when one branch accepts, the concatenation gadget accepts exactly when a word splits into a word accepted by the first machine followed by one accepted by the second, and the star gadget accepts exactly when the input is a concatenation of finitely many words accepted by the submachine. Using [L1] and the uniqueness from [L2], the induction follows for every constructor.

Hence the constructed epsilon-NFA $N_R$ recognizes precisely $\mathcal{L}(R)$.