\begin{frame}{Word (String) Matching (Thompson, 1968)}
  \begin{goal}{}
  The input:
  \begin{itemize}\setlength{\itemsep}{0pt}
    \item a word $u$
    \item a regular expression $r$
  \end{itemize}
  \smallskip
  \emph{Question:} Does $u$ contain a subword in $L(r)$?
  \end{goal}
  \pause\medskip
  
  The following algorithm answers this question.
  \begin{block}{}
    \begin{enumerate}
    \item Transform the regular expression \alert{$\Sigma^*\cdot r$} into an NFA.
    \item Compute `\emph{on-the-fly}' path of $u$ in the corresponding DFA.
    \item Terminate as soon as a final state is reached.
    \end{enumerate}
    
  \end{block}
  The algorithm is used for example in \text{grep} in Unix.
  \pause
  \smallskip

  \begin{goal}{}
  \structure{Worst-case time complexity}: $O(|r|{\cdot}|u|)$
  \end{goal}
\end{frame}