\begin{frame}{Decidability of Emptyness}
  \begin{goal}{}
    Roughly speaking, a property is \emph{decidable} if there is an \emph{algorithm/program} that can tell whether the property holds.
  \end{goal}
  \pause

  \begin{alertblock}{Convention}
    If we say that a \emph{property of regular languages is decidable}, 
    we implicitly assume that the language is \emph{given as a DFA} (or a description that can be translated into a DFA by an algorithm).
  \end{alertblock}
  \pause\bigskip

  \begin{block}{Theorem}
    It is decidable whether a regular language $L$ is empty.
  \end{block}
  \pause
  
  \begin{proof}
    \begin{itemize}\setlength{\itemsep}{0ex}
      \item Construct a DFA (or NFA) $M$ with $L(M)=L$.
      \item Check if $M$ has a path from starting state to a final state.
      \item If \emph{yes}, then $L \ne \emptyset$. If \emph{no}, then $L = \emptyset$.
       \qedhere
    \end{itemize}
  \end{proof}
  
\end{frame}