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

    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).

    It is decidable whether a regular language $L$ is empty.
      \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$.