\begin{frame}{Decidability of Membership}

  \begin{goal}{Theorem}
    It is decidable if a word $u$ is member of a regular language $L$.
  \end{goal}
  \pause
  
  \begin{proof}
    \begin{itemize}
     \item Represent $L$ in the form of a DFA $M$.
     \item Check if $u$ is accepted by $M$. \qedhere
    \end{itemize}
  \end{proof}
  \pause\bigskip
  
  \begin{alertblock}{Practical difficulty: state-space explosion}
    The conversion to DFA might require an exponential number of states.
    (E.g. when $L$ is given as NFA or regular expression.)
  \end{alertblock}
  \pause
  \begin{goal}{Solution}
    \emph{On-the-fly} generation of DFA prevents state-space explosion.
    We only generate those states visited when reading $u$.
  \end{goal}
\end{frame}