\begin{frame}{NFAs with a Single Starting State}
  \begin{goal}{}
    For every NFA $M$ there is an NFA $N$ such that 
    $L(M) = L(N)$
    and $N$ has a \emph{single starting state}.
  \end{goal}
  \pause
  
  \begin{block}{Construction}
    Let $N = (Q,\Sigma,\delta,S,F)$ be an NFA.
    \pause\medskip

    Define $M$ the be obtained from $N$ as follows
    \begin{itemize}
    \pause
      \item add a fresh state $q_0$,
    \pause
      \item add transitions $q_0 \stackrel{\lambda}{\to} q$ for every $q \in S$, and
    \pause
      \item make $q_0$ the only starting state of $M$.
    \end{itemize}
    \pause
    Then $M$ has a single starting state and $L(N)= L(M)$.
  \end{block}
  \pause
  
  \begin{goal}{Convention}
    We denote NFAs $(Q,\Sigma,\delta,S,F)$ with a single starting state $S = \{\, q_0 \,\}$ by $(Q,\Sigma,\delta,q_0,F)$.
  \end{goal}
\end{frame}