\begin{frame}{DFAs and NFAs are Equally Expressive}
  \begin{block}{Theorem}
    A language $L$ is accepted by a \alert{NFA} 
    $\iff$ $L$ is \alert{regular}.
  \end{block}
  
  \pause
  \begin{construction}[Powerset]
    Let $M = (Q,\Sigma,\delta,S,F)$ be a NFA.
    \pause\smallskip

    \emph{Idea:} state of DFA = set of all states the NFA can be in
    \pause\smallskip

    We construct a DFA $N = (Q',\Sigma,\delta',q_0',F')$ where
    \begin{talign}
    Q' &= \mpause[1]{2^Q = \{\, X \mid X \subseteq Q \,\}} \\[-1.5mm]
    \delta'(X,a) &= \mpause{ \{\, q' \in Q \mid q \apath{a} q' \mbox{ for some }q\in X \,\} } \\[-1mm]
    q_0' &= \mpause{ \{\, q' \in Q \mid q \apath{\lambda} q' \mbox{ for some }q\in S \,\} }  \\[0mm]
    F' &= \mpause{ \{\, X \subseteq Q \mid X \cap F \neq \emptyset \,\} }
    \end{talign}
    \pause\pause\pause\pause\pause
    For every $w \in \Sigma^*$ and $X \subseteq Q$ it holds that\vspace{-1mm}
    \begin{talign}
      \alert{X \apath{w} X' \text{ in $N$} \;\; \iff \;\; X' = \{\, q' \mid q \in X,\; q \apath{w} q' \text{ in $M$} \,\}}
    \end{talign}
    From this property it follows that $L(N) = L(M)$.
  \end{construction}
\end{frame}