22/35

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