\begin{frame}{Nondeterministic Finite Automata} \begin{goal}{} NFAs are defined like DFAs, except that NFAs allow for: \begin{itemize} \item \emph{Multiple starting states}. \item \emph{Any number of outgoing arrows} with the same label. \item \emph{Empty steps}: arrows labelled $\lambda$ (do not consume input). \end{itemize} \end{goal} \begin{exampleblock}{} \begin{center} \vspace{-.5ex} \input{tikz/nfa1.tex} \vspace{-1ex} \end{center} Note that: \begin{itemize} \item both $q_0$ and $q_2$ are starting states \item the state $q_1$ has two outgoing arrows with label $b$ \item there is an empty step from $q_0$ to $q_1$ \end{itemize} \end{exampleblock} \end{frame}