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