\begin{frame}{Regular Expressions} \begin{block}{} We define the \emph{regular expressions} over an alphabet $\Sigma$: \begin{itemize} \item \alert{$\emptyset$} is a regular expression \item \alert{$\lambda$} is a regular expression \item \alert{$a$} is a regular expression for every $a \in \Sigma$ \item \alert{$r_1+r_2$} is a regular expression for all regular expr.\ $r_1$ and $r_2$ \item \alert{$r_1\cdot r_2$} is a regular expression for all regular expr.\ $r_1$ and $r_2$ \item \alert{$r^*$} is a regular expression for all regular expressions $r$ \end{itemize} \end{block} \pause\medskip A regular expression is syntax, describing a language. \begin{goal}{} Every \emph{regular expression} $r$ defines a \emph{language} $L(r)$: \begin{talign} L(\emptyset) &= \emptyset & L(r_1 + r_2) &= L(r_1) \cup L(r_2) \\ L(\lambda) &= \{\, \lambda \,\} & L(r_1 \cdot r_2) &= L(r_1) L(r_2) \\ L(a) &= \{\, a \,\} \text{\;\; for $a\in\Sigma$} & L(r^*) &= L(r)^* \end{talign} \end{goal} \end{frame}