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