\begin{frame}{Word (String) Matching (Thompson, 1968)}
  The input:
    \item a word $u$
    \item a regular expression $r$
  \emph{Question:} Does $u$ contain a subword in $L(r)$?
  The following algorithm answers this question.
    \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.
  The algorithm is used for example in \text{grep} in Unix.

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