\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}