17/38
\begin{frame}{($\Leftarrow$) From Regular Expressions to NFAs}
\begin{construction}[$\Leftarrow$]
For every regular expression $r$,
we build an NFA $M$ such that
\begin{itemize}\setlength{\itemsep}{0pt}
\item $L(M) = L(r)$,
\item $M$ has precisely one final and one (different) starting state
\end{itemize}
\pause
We construct $M$ by induction (recursion) on $r$.
\begin{center}\vspace{-1ex}
\begin{tikzpicture}[default,node distance=12mm,->,s/.style={minimum size=5mm}]
\begin{scope}
\mpause[1]{
\node (q0) [state,s] {}; \draw ($(q0) + (-8mm,0mm)$) -- (q0);
\node (q1) [fstate,s,right of=q0] {};
}
\node [left of=q0,anchor=east,node distance=9mm] {$\emptyset$:};
\end{scope}

\begin{scope}[yshift=-16mm]
\mpause{
\node (q0) [state,s] {}; \draw ($(q0) + (-8mm,0mm)$) -- (q0);
\node (q1) [fstate,s,right of=q0] {};

\draw (q0) to node [above] {$\lambda$} (q1);
}
\node [left of=q0,anchor=east,node distance=9mm] {$\lambda$:};
\end{scope}

\begin{scope}[yshift=-32mm]
\mpause{
\node (q0) [state,s] {}; \draw ($(q0) + (-8mm,0mm)$) -- (q0);
\node (q1) [fstate,s,right of=q0] {};

\draw (q0) to node [above] {$a$} (q1);
}
\node [left of=q0,anchor=east,node distance=9mm] {$a$:};
\end{scope}

\begin{scope}[xshift=45mm,yshift=-0mm]
\mpause{
\node (q0) [state,s] {}; \draw ($(q0) + (-8mm,0mm)$) -- (q0);
\subnfa{r_1}{$(q0)+(10mm,5mm)$}
\subnfa{r_2}{$(q0)+(10mm,-5mm)$}
\node (qf) at ($(r_1f)!0.5!(r_2f) + (10mm,0mm)$) [fstate,s] {};

\draw (q0) to node [above,pos=.4] {$\lambda$} (r_1s);
\draw (q0) to node [below,pos=.4] {$\lambda$} (r_2s);
\draw (r_1f) to node [above,pos=.4] {$\lambda$} (qf);
\draw (r_2f) to node [below,pos=.4] {$\lambda$} (qf);
}
\node [left of=q0,anchor=east,node distance=9mm] {$r_1 + r_2$:};
\end{scope}

\begin{scope}[xshift=45mm,yshift=-16mm]
\mpause{
\subnfa{r_1}{$(0mm,0mm)$}
\draw ($(r_1s) + (-8mm,0mm)$) -- (r_1s);
\subnfafinal{r_2}{$(r_1f)+(10mm,0mm)$}

\draw (r_1f) to node [above,pos=.4] {$\lambda$} (r_2s);
}
\node [left of=r_1s,anchor=east,node distance=9mm] {$r_1 \cdot r_2$:};
\end{scope}

\begin{scope}[xshift=45mm,yshift=-32mm]
\mpause{
\node (q0) [state,s] {}; \draw ($(q0) + (-8mm,0mm)$) -- (q0);
\subnfa{r}{$(q0)+(10mm,0mm)$}
\node (qf) at ($(rf) + (10mm,0mm)$) [fstate,s] {};

\draw (q0) to node [above,pos=.4] {$\lambda$} (rs);
\draw (rf) to node [above,pos=.4] {$\lambda$} (qf);

\draw (q0) to[out=70,in=120,looseness=.4] node [above,label] {$\lambda$} (qf);
\draw (qf) to[out=180+60,in=180+130,looseness=.4] node [below,label] {$\lambda$} (q0);
}
\node [left of=q0,anchor=east,node distance=9mm] {$r^*$:};
\end{scope}
\end{tikzpicture}
\end{center}\vspace{-2ex}
\end{construction}
\end{frame}