111/122
\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}