\begin{slide}{Sätze über reguläre Sprachen}

Für jede Sprache $L$ sind die folgenden Aussagen äquivalent:
\begin{itemize}
\item
  es gibt einen regulären Ausdruck $X$ mit $L=\Lang(X)$,
\item
  es gibt eine Typ-3-Grammatik $G$ mit $L=\Lang(G)$,
\item
  es gibt einen endlichen Automaten $A$ mit $L=\Lang(A)$.
\end{itemize}

Beweispläne: 
\begin{itemize}\itemsep 2pt
\item Grammatik $\leftrightarrow$ Automat 
  (Variable $=$ Zustand)
\item Ausdruck $\rightarrow$ Automat
    (Teilbaum $=$ Zustand)
\item Automat $\rightarrow$ Ausdruck 
  (dynamische Programmierung)

  $L_A(p,q,r)=$ alle Pfade von $p$ nach
  $r$ über Zustände $\le q$.
\end{itemize}



\end{slide}
