\begin{frame}{($\Rightarrow$) From NFAs to Regular Expressions (1)} \begin{construction}[$\Rightarrow$] For every NFA $M$, we construct a regular expression $r$ with \begin{talign} L(r) = L(M) \end{talign} \pause \emph{Step 1:} \smallskip We transform $M$ such that there is \begin{itemize} \item precisely one initial state \item precisely one final state \end{itemize} % \pause\medskip % % If $M$ has multiple final states: % \begin{itemize}\setlength{\itemsep}{0pt} % \item add a fresh state \alert{$q_f$} to $M$, % \item add an arrow \alert{$q \stackrel{\lambda}{\to} q_f$} for every \alert{final state $q$}, and % \item make $q_f$ the only final state. % \end{itemize} % \pause\medskip % % Now $M$ has precisely one final state ($\#F = 1$). \end{construction} \vspace{10cm} \end{frame}