\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}