\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}