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

\begin{slide}{Reduzierte Automaten}

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

Ein Zustand $q$ eines Automaten $A$ heißt
\begin{itemize} \itemsep 2pt
\item \emph{erreichbar}, falls von $q$ von einem Startzustand aus
 erreichbar ist: $\exists w \in \Sigma^*, s \in S(A): s \stackrel{w}{\to} q$.
\item \emph{produktiv}, falls von $q$ aus ein akzeptierender Zustand
  erreichbar ist: $\exists w \in \Sigma^*, f \in F(A): q \stackrel{w}{\to} f$.
\item \emph{nützlich}, wenn er erreichbar \emph{und} produktiv ist.
\end{itemize}

$A$ heißt \emph{reduziert},
wenn alle Zustände nützlich sind. 

\emph{Satz}: Zu jedem Automaten $A$ gibt es einen reduzierten Automaten $B$
mit $L(A)=L(B)$.

\emph{Beweis}: \\
erst $A$ auf erreichbare Zustände einschränken, ergibt $A'$,\\
dann $A'$ auf produktive Zustände einschränken, ergibt $B$.

\end{slide}
