<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\begin{slide}{Potenzmengen-Konstruktion}

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

\begin{itemize}\itemsep0pt
\item Eingabe: ein (nicht-det.) Automat $A = (Q,S,F,T)$
\item Ausgabe: ein vollst. det. Automat $A'$ mit $L(A')=L(A)$.
\end{itemize}

Idee: betrachten Mengen von erreichbaren ZustÃ¤nden

$A' = (Q',S',F',T')$ mit
\begin{itemize}\itemsep0pt
\item $Q' = 2^Q$ (Potenzmenge - daher der Name)
\item $(p', c, q') \in T' 
  \iff q' = \{ q \mid \exists p \in p': p \stackrel{c}{\to}_A q \}$
\item $S' = \{ S \}$
\item $F' = \{ q' \mid q' \in Q' \wedge q' \cap F \neq \emptyset \}$
\end{itemize}


\end{slide}
</pre></body></html>