\begin{frame}{($\Rightarrow$) From NFAs to Regular Expressions (1)}
    For every NFA $M$,
    we construct a regular expression $r$ with 
      L(r) = L(M)
    \emph{Step 1:} 
    We transform $M$ such that there is
      \item precisely one initial state
      \item precisely one final state
%     \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$).