83/122
\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}