%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\begin{slide}{Reguläre Sprachen/Ausdrücke}


Die Menge $E(\Sigma)$ der \emph{regulären Ausdrücke} \\
über einem Alphabet (Buchstabenmenge) $\Sigma$ \\
ist die kleinste Menge $E$, für die gilt:
\begin{itemize} \itemsep 1pt \parskip 1pt
\item für jeden Buchstaben $x \in \Sigma: x\in E$

  (autotool: Ziffern oder Kleinbuchstaben)
\item das leere Wort $\epsilon \in E$ (autotool: \verb|Eps|)
\item die leere Menge $\emptyset \in E$ (autotool: \verb|Empty|)
\item wenn $A, B\in E$, dann 
  \begin{itemize}
  \item (Verkettung) $A \cdot B \in  E$ (autotool: \verb|*| oder weglassen)
  \item (Vereinigung) $A + B \in E$ (autotool: \verb|+|)
  \item (Stern, Hülle) $A^* \in E$ (autotool: \verb|^*|)
  \end{itemize}
\end{itemize}
Jeder solche Ausdruck beschreibt eine \emph{reguläre Sprache}.

\end{slide}

\begin{slide}{Beispiele/Aufgaben zu regulären Ausdrücken}

Wir fixieren das Alphabet $\Sigma=\{a,b\}$.

\begin{itemize}
\item
  alle Wörter, die mit $a$ beginnen und mit $b$ enden:
  $a \Sigma^* b$.
\item
  alle Wörter, die wenigstens drei $a$ enthalten
  $\Sigma^* a \Sigma^* a \Sigma^* a \Sigma^*$
\item
  alle Wörter mit gerade vielen $a$
  und beliebig vielen $b$?
\item
  Alle Wörter, die ein $aa$ oder ein $bb$ enthalten:
  $\Sigma^* (aa \cup bb) \Sigma^*$
\item
  (Wie lautet das Komplement dieser Sprache?)
\end{itemize}

\end{slide}
