22/24
\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}