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

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