\begin{slide}{Automaten (Operationen: Komplement)}

Eingabe: $A_1=(\Sigma,Q_1,I_1,\delta_1,F_1)$,

Ausgabe: $A$ mit 
$\Lang(A)=\Sigma^* \setminus \Lang(A_1)$

Lösung durch Potenzmengen-Konstruktion:
$A=(\Sigma,Q,I,\delta,F)$ mit

\begin{itemize}
\item $Q=2^{Q_1}$ (daher der Name)
\item $I = \{ I_1 \}$, $F=2^{Q_1\setminus F_1}$
\item $\delta(c)(M)=\dots$
\end{itemize}

Korrektheit:
$\forall w\in\Sigma^*: w\in\Lang(A)\iff
w\notin\Lang(A_1)$

\bigskip

Komplexität: $|Q| = 2^{|Q_1|}$
(hier: Zeit $=$ Platz)

\end{slide}
