22/122
\begin{frame}{Decidability of Membership}

\begin{block}{Theorem}
It is decidable if a word $u$ is member of a regular language $L$.
\end{block}

\begin{proof}
\begin{enumerate}
\item Represent $L$ in the form of a DFA $M$.
\item Check if $u$ is accepted by $M$. \qedhere
\end{enumerate}
\end{proof}
\pause\bigskip

(E.g. when $L$ is given as NFA or regular expression.)
We only generate those states visited when reading $u$.