\begin{frame}{Nondeterministic Finite Automata}
  \begin{block}{}
    A \emph{nondeterministic finite automaton}, short \emph{NFA}, consists of:
    
    \begin{itemize}
      \item
      a finite set $Q$ of states
      \item
      a finite input alphabet $\Sigma$
      \item
      a transition function $\delta : Q \times (\Sigma \,\alert{\cup\{\lambda\}}) \to \alert{2^Q}$
      \item
      a set \alert{$S \subseteq Q$} of starting states
      \item
      a set $F \subseteq Q$ of final states
      \smallskip
    \end{itemize}
  \end{block}
  Here $2^Q$ is the set of all subsets of $Q$: $2^Q = \{\, X \mid X \subseteq Q\,\}$.

  \begin{exampleblock}{}
    The NFA on the preceding slide is $M = (Q,\Sigma,\delta,S,F)$ where\\[1ex]
    \begin{minipage}{.5\textwidth}
      \hspace*{1cm}$Q = \{\, q_0,q_1,q_2 \,\}$\\
      \hspace*{1cm}$\Sigma = \{\, a,b \,\}$\\
      \hspace*{1cm}$S = \{\, q_0,q_2 \,\}$\\
      \hspace*{1cm}$F = \{\, q_1 \,\}$
    \end{minipage}
    \begin{minipage}{.49\textwidth}
      {\renewcommand{\arraystretch}{1}
      \begin{tabular}{c|ccc}
        $\delta$ & $q_0$ & $q_1$ & $q_2$ \\
        \hline
        $a$ & $\{\,q_1\,\}$ & $\emptyset$ & $\{\,q_0\,\}$ \\
        $b$ & $\emptyset$ & $\{\,q_1,q_2\,\}$ & $\emptyset$ \\
        $\lambda$ & $\{\,q_1\,\}$ & $\emptyset$ & $\emptyset$
      \end{tabular}}
    \end{minipage}
  \end{exampleblock}
\end{frame}