\begin{slide}{Ableitungen (1)}

(algebraische Methoden, angewendet auf reguläre Ausdrücke)

Analogie zwischen
\begin{itemize}
\item partieller Ableitung
 $\frac{\partial xy}{\partial x} = y$
\item Prozeß-Übergang
  $(x \to (y \to \STOP)) \stackrel{x}{\to} (y \to \STOP)$
\end{itemize}
Übung: Ableitung einer Summe? eines Produktes?

\bigskip


\end{slide}

\newcommand{\Lang}{\operatorname{Lang}}

\begin{slide}{Ableitungen (2)}

definiere Relation $X_1 \stackrel{a}{\to} X_2$

für Ausdrücke $X_1, X_2$ und Zeichen $a\in\Sigma$

\bigskip

bestimme alle von $X$ durch
$\stackrel{a}{\to}$-Pfade erreichbaren Ausdrücke.

der so definierte Graph ist ein endlicher Automat
für $\Lang(X)$

\bigskip

man erhält ein Verfahren zur Automaten-Synthese:
\begin{itemize}
\item Eingabe: regulärer Ausdruck $X$
\item Ausgabe: endlicher Automat $A$ mit $\Lang(A) = \Lang(X)$
\end{itemize}
und $A$ ist sogar vollständig und deterministisch.


\end{slide}

\begin{slide}{Ableitungen (3)}

  Syntax (einfacher) regulärer Ausdrücke:
  \begin{itemize}
  \item elementar reguläre Ausdrücke

    Buchstabe, leeres Wort, leere Menge
  \item zusammengesetzte reguläre Ausdrücke

    Vereinigung, Verkettung, Wiederholung
  \end{itemize}
  definiere durch Rekursion über diese Syntax
  \begin{itemize}
  \item Prädikat $E(X)$, Spezifikation: $E(X) \iff \epsilon \in \Lang(X)$
  \item Nachfolger $\frac{\partial X}{\partial a}$,

    Spezifikation: 
    $\Lang(\frac{\partial X}{\partial a}) = \{ w \mid a\cdot w \in \Lang(X)\}$
  \end{itemize}

\end{slide}

\begin{slide}{Ableitungen (4)}
  \begin{itemize}
\item Ableitung eines Buchstabens

 $ \frac{\partial b}{\partial a} = $
 (wenn $a=b$ dann $\epsilon$  sonst $\emptyset$)
\item Ableitung des leeren Wortes

 $ \frac{\partial \epsilon}{\partial a} = \emptyset$

\item Ableitung der leeren Menge

 $ \frac{\partial \emptyset}{\partial a} = \emptyset$
\end{itemize}



\end{slide}

\begin{slide}{Ableitungen (5)}
  \begin{itemize}
  \item 
Ableitung einer Vereinigung:

 $ \frac{\partial (X + Y)}{\partial a} = 
 \frac{\partial X}{\partial a} 
+ \frac{\partial Y}{\partial a}$
\item
Ableitung einer Verkettung: $ \frac{\partial (X\cdot Y)}{\partial a} = \dots$
\begin{itemize}
\item wenn $\neg E(X)$, 
dann $\dots = \frac{\partial X}{\partial a} \cdot Y$
\item wenn $E(X)$, 
dann $\dots = \frac{\partial X}{\partial a} \cdot Y +
  \frac{\partial Y}{\partial a}$
\end{itemize}
\item
Ableitung einer Wiederholung:

 $ \frac{\partial (X^*)}{\partial a} = 
 \frac{\partial (X)}{\partial a}\cdot X^* $
  \end{itemize}

Vereinfachungsregeln für $\epsilon$ und $\emptyset$
als Argumente für $+$ und $\cdot$


\end{slide}
