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