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