\begin{frame}{Finite Languages are Regular}
  \begin{block}{Theorem}
    Every \emph{finite} language $L$ regular.
  \end{block}
  \pause
  
  \begin{block}{Construction}
    Let $N$ be the length of the longest word in $L$.
    \pause\bigskip
    
    Define the DFA $M = (Q,\Sigma,\delta,q_\lambda,F)$ by
    \begin{itemize}
    \pause
      \item $Q = \{\, q_w \mid w \in \Sigma^*,\; |w| \le N \,\} \cup \{\, q_\bot \,\}$
    \pause
      \item $F = \{\, q_w \mid w \in L \,\}$
    \pause
      \item 
        the transition function $\delta$ is defined by
        \begin{talign}
          \delta(q_w,a) = 
            \begin{cases}
              q_{wa} &\text{if $|wa| \le N$},\\
              q_\bot &\text{if $|wa| > N$}
            \end{cases} 
          &&  
          \delta(q_\bot,a) = q_\bot
        \end{talign}
        for every $w \in \Sigma^*$ with $|w| \le N$ and $a \in \Sigma$
    \end{itemize}
    
  \end{block}
\end{frame}

\themex{Nondeterministic Finite Automata}