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

Eingabe: $A_1=(\Sigma,Q_1,I_1,\delta_1,F_1),
A_2=(\Sigma,Q_2,I_2,\delta_2,F_2)$,

Ausgabe: $A$ mit $\Lang(A)=\Lang(A_1)\cap\Lang(A_2)$

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

\begin{itemize}
\item $Q=Q_1\times Q_2$ (daher der Name)
\item
$I=I_1\times I_2, F=F_1\times F_2$
\item $\delta(c)((p_1,p_2),(q_1,q_2)) = \dots$
\end{itemize}

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

\bigskip

Komplexität: $|Q| = |Q_1|\cdot |Q_2|$ 
(hier: Zeit $=$ Platz)

\end{slide}
