\begin{frame}{Word Matching Example}

  Regular expression \alert{$r=a(aa^*b+bb^*a)b$} gives rise to the NFA:
  \begin{center}
    \begin{tikzpicture}[default,node distance=18mm,->]
      \node (q0) [state] {$q_0$}; \draw ($(q0) + (-10mm,0mm)$) -- (q0); 
      \node (q1) [state,right of=q0] {$q_1$};
      \node (q2) [state,right of=q1] {$q_2$};
      \begin{scope}[node distance=16mm]
      \node (q3) [state,right of=q2,yshift=9mm] {$q_3$};
      \node (q4) [state,right of=q2,yshift=-9mm] {$q_4$};
      \node (q5) [state,right of=q3,yshift=-9mm] {$q_5$};
      \end{scope}
      \node (q6) [fstate,right of=q5] {$q_6$};

      \draw (q0) to[tloop] node [label,above] {$a$} (q0);
      \draw (q0) to[bloop] node [label,below] {$b$} (q0);
      \draw (q0) to node [label,above] {$\lambda$} (q1);
      \draw (q1) to node [label,above] {$a$} (q2);
      \draw (q2) to node [label,above left] {$a$} (q3);
      \draw (q2) to node [label,below left] {$b$} (q4);
      \draw (q3) to[tloop] node [label,above] {$a$} (q3);
      \draw (q4) to[tloop] node [label,above] {$b$} (q4);
      \draw (q3) to node [label,above right] {$b$} (q5);
      \draw (q4) to node [label,below right] {$a$} (q5);
      \draw (q5) to node [label,above] {$b$} (q6);
    \end{tikzpicture}
  \end{center}
  \pause\medskip
 
  We match $r$ with \alert{$u=aaababbb$}.
  \pause
  \begin{center}
    \begin{tikzpicture}[default,node distance=18mm,->,s/.style={inner sep=0mm}]
      \node (q0) [state,s] {$01$}; \draw ($(q0) + (-10mm,0mm)$) -- (q0); 
      \mpause[1]{ 
        \node (q1) [state,s,anchor=west] at ($(q0.east) + (5mm,0mm)$) {$012$}; 
        \draw (q0) to node [label,above] {$a$} (q1);
      }
      \mpause{ 
        \node (q2) [state,s,anchor=west] at ($(q1.east) + (5mm,0mm)$) {$0123$}; 
        \draw (q1) to node [label,above] {$a$} (q2);
      }
      \mpause{
        \draw (q2) to[tloop] node [label,above] {$a$} (q2);
      }
      \mpause{ 
        \node (q3) [state,s,anchor=west] at ($(q2.east) + (5mm,0mm)$) {$0145$}; 
        \draw (q2) to node [label,above] {$b$} (q3);
      }
      \mpause{
        \node (q4) [state,s,anchor=west] at ($(q3.east) + (5mm,0mm)$) {$0125$}; 
        \draw (q3) to node [label,above] {$a$} (q4);
      }
      \mpause{ 
        \node (q5) [fstate,s,anchor=west] at ($(q4.east) + (5mm,0mm)$) {$0146$}; 
        \draw (q4) to node [label,above] {$b$} (q5);
      }
    \end{tikzpicture}
  \end{center}
  \pause\pause\pause\pause\pause\pause\pause
  \[
  \begin{array}{cccccccccccccccc}
  & a && a && \malert{8}{1}{a} && \malert{8}{1}{b} && \malert{8}{1}{a} && \malert{8}{1}{b} && b && b \\
  \mpause[1]{q_0} && \mpause[7]{q_0} && \mpause[6]{q_0}\mpause[5]{q_1} && \mpause[4]{q_2} && \mpause[3]{q_4} && \mpause[2]{q_5} && \mpause[1]{q_6} && \hphantom{q_6}
  \end{array}
  \]
  \vspace{10cm}
\end{frame}