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