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

\begin{slide}{Deteministische Automaten}

\kopf{$ $Id: det.tex,v 1.1 2011-10-16 14:06:16 waldmann Exp $ $}

\begin{itemize}\itemsep 0pt
\item
  $A$ heißt \emph{vollständig}, wenn es  zu jedem $(p,c)$ wenigstens ein $q$
  mit  $p \stackrel{c}{\to}_A q$ gibt.
\item
  $A$ heißt \emph{deterministisch}, falls
  \begin{itemize}\itemsep 0pt
  \item
    die Start-Menge $S(A)$ genau ein Element enthält und
  \item
    die Relation $T(A)$ sogar eine partielle Funktion ist
    (d. h. zu jedem $(p,c)$ gibt es höchstens ein $q$
    mit  $p \stackrel{c}{\to}_A q$.
  \end{itemize}
  Dann gibt es in $A$
  für jedes Wort $w$ höchstens einen mit $w$ beschrifteten Pfad
  vom Startzustand aus.
\end{itemize}

\emph{Satz}: Zu jedem Automaten $A$ gibt es einen deterministischen
und vollständigen Automaten $D$ mit $L(A)=L(D)$.



\end{slide}
