\begin{frame}{NFAs Reading Words} Let $M = (Q,\Sigma,\delta,S,F)$ be a NFA. % \begin{block}{} % A \emph{configuration} of $M$ is a pair $(q,w)$ with $q \in Q$ and $w \in \Sigma^*$. % \end{block} \begin{block}{} The \emph{step relation $\vdash$} of $M$ is defined on configurations by \begin{talign} (q,\alert{\alpha} w) \vdash (q',w) \quad \text{if $\alert{q' \in} \delta(q,\alert{\alpha})$ with $\alpha \in \Sigma \alert{\cup\{\lambda\}}$} \end{talign} \end{block} \pause Note that if $\alpha = \lambda$, then \begin{itemize} \item the state changes ($q$ to $q'$), but \item the input word stays the same ($\lambda w = w$). \end{itemize} \pause\medskip \begin{exampleblock}{} \begin{center} \vspace{-.5ex} \input{tikz/nfa1.tex} \vspace{-1.5ex} \end{center} \begin{talign} (q_0,abbab) &\vdash (q_1,bbab) \vdash (q_1,bab) \vdash (q_2,ab) \\ &\vdash (q_0,b) \vdash (q_1,b) \vdash (q_1,\lambda) \end{talign} \end{exampleblock} \end{frame}