\begin{frame}{Decidability of Membership}

    It is decidable if a word $u$ is member of a regular language $L$.

     \item Represent $L$ in the form of a DFA $M$.
     \item Check if $u$ is accepted by $M$. \qedhere
  \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.)
    \emph{On-the-fly} generation of DFA prevents state-space explosion.
    We only generate those states visited when reading $u$.