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

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

Die Menge aller möglichen Werte einer Tokenklasse
ist üblicherweise eine reguläre Sprache,
und wird (extern) durch eine regulären Ausdruck beschrieben.

\bigskip

Die folgenden Aussagen sind äquivalent:
\begin{itemize}
\item $L$ wird von einem regulären Ausdruck erzeugt.
\item $L$ wird von einer rechtslinearen Grammatik erzeugt.
  (Chomsky-Typ 3)
\item $L$ wird von einem endlichen Automaten akzeptiert.
\item $L$ wird von einem endlichen deterministischen Automaten akzeptiert.
\end{itemize}

\end{slide}

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

\dots über einem Alphabet $\Sigma$
ist die kleinste Menge $E$ mit:
\begin{itemize} \itemsep 0pt
 \item atomare Ausdrücke:
  \begin{itemize}
\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|)
\end{itemize}
\item zusamenngesetzte Ausdrücke: 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}

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