\begin{frame}{Paths in NFAs}
  Let $M = (Q,\Sigma,\delta,S,F)$ be a NFA. 
  \begin{block}{}
    For a word $w$, we write 
    \begin{talign}
      \alert{q \apath{w} q'}
    \end{talign}
    if $w = \alpha_1 \cdots \alpha_n$ for some $\alpha_1, \ldots, \alpha_n \in (\Sigma \alert{\cup \{\lambda\}})$
    and there are states $q_1,\ldots,q_{n-1}$ such that 
    \begin{talign}
      q \stackrel{\alpha_1}{\to} q_1 \quad\quad
      q_1 \stackrel{\alpha_2}{\to} q_2 \quad\quad
      q_2 \stackrel{\alpha_3}{\to} q_3 \quad\quad
      \ldots \quad\quad
      q_{n-1} \stackrel{\alpha_n}{\to} q'
    \end{talign}
  \end{block}
  \pause
  \begin{exampleblock}{}
    \centerline{
    \begin{tikzpicture}[default,node distance=15mm,->]
      \node (q0) [state] {$q_0$}; \draw ($(q0) + (-10mm,0mm)$) -- (q0); 
      \node (q1) [fstate,right of=q0] {$q_1$};
      \node (q2) [state,right of=q1] {$q_2$}; \draw ($(q2) + (10mm,0mm)$) -- (q2);
      \draw (q0) to[bend left=10] node [label,above] {$a$} (q1);
      \draw (q0) to[bend left=-10] node [label,below] {$\lambda$} (q1);
      \draw (q1) to[bend left=0] node [label,above] {$b$} (q2);
      \draw (q1) to[tloop] node [label,above] {$b$} (q1);
      \draw (q2) to[out=-120,in=-60,looseness=0.5] node [label,below] {$a$} (q0);
      \begin{scope}[nodes={rectangle}]
        \node at (5.7cm,0.2cm) [align=left] {
          $q_0 \apath{\lambda} q_0$\\[0mm]
          $q_0 \apath{\lambda} q_1$\\[0mm]
          $q_1 \apath{b} q_1$\\[0mm]
          $q_1 \apath{b} q_2$
        };
      \end{scope}
      \begin{scope}[nodes={rectangle}]
        \node at (8.5cm,0.2cm) [align=left] {
          $q_1 \apath{ba} q_0$\\[0mm]
          $q_1 \apath{ba} q_1$\\[0mm]
          $q_0 \apath{abbab} q_1$\\[0mm]
          $q_0 \apath{abbab} q_2$
        };
      \end{scope}
    \end{tikzpicture}\quad
    }
  \end{exampleblock}
  \pause
  
  \begin{goal}{}
    Theorem: \;\;$q \apath{w} q' \;\iff\; (q,w) \vdash^* (q',\lambda)$.
  \end{goal}
\end{frame}