\begin{frame}{Regular Languages: Union}
  \begin{block}{Theorem}
    If $L_1$ and $L_2$ are regular, then \alert{$L_1 \cup L_2$} is regular.
  \end{block}
  \pause
  
  \begin{construction}[Product]
    There exists a DFAs  
    \begin{talign}
      M_1 = (Q_1,\Sigma,\delta_1,q_{0,1},F_1) &&
      M_2 = (Q_2,\Sigma,\delta_2,q_{0,2},F_2) 
    \end{talign}
    such that $L(M_1) = L_1$ and $L(M_2) = L_2$.
    \pause\medskip
    
    \emph{Idea:} We run $M_1$ and $M_2$ in parallel.
    \pause\medskip
    
    We define a DFA $N = (Q, \Sigma, \delta, q_0, F)$ where
    \begin{itemize}\setlength{\itemsep}{0pt}
      \pause
      \item $Q =\pause Q_1 \times Q_2 = \{\,(q_1,q_2) \mid q_1 \in Q_1,\; q_2 \in Q_2\,\}$ 
      \pause
      \item $\delta((q_1,q_2),a) =\pause (\delta_1(q_1,a),\;\delta_2(q_2,a))$ 
      \pause
      \item $q_0 =\pause (q_{0,1},\; q_{0,2})$ 
      \pause
      \item $F =\pause \{\, (q_1,q_2) \in Q \mid q_1 \in F_1 \text{ or } q_2 \in F_2 \,\}$ 
    \end{itemize}
    \pause
    Then it follows that $L(N) = L(M_1) \cup L(M_2) = L_1 \cup L_2$.
  \end{construction}  
\end{frame}