\begin{frame}{Example} \begin{example} $L((a+b) \cdot c^*) = (\{\,a\,\} \cup \{\,b\,\}) \{\,c\,\}^* = \{\,a,b\,\} \{\,c\,\}^*$ \end{example} \pause\bigskip \begin{goal}{} Regular expressions are used to search and manipulate text. \end{goal} \medskip \begin{minipage}{.7\textwidth} For example: \begin{itemize} \item \texttt{grep} in Linux \item script languages such as Perl \end{itemize} \end{minipage} \begin{minipage}{.29\textwidth} \includegraphics[height=12mm]{images/regular-expressions.jpg} \end{minipage} \medskip Every major programming language has regular expressions. \pause\bigskip\medskip \begin{exampleblock}{Exercise} Find a regular expression $r$ over $\Sigma = \{\,a,b\,\}$ such that\\ $L(r)$ consists of all words that contain the pattern \alert{$bab$}: \pause \begin{talign} (a+b)^* \cdot b\cdot a\cdot b \cdot (a+b)^* \mpause[1]{= (a+b)^* \; bab \; (a+b)^*} \end{talign} \end{exampleblock} \end{frame}