equal
deleted
inserted
replaced
226 \underline{language}\\ wrt to a character \bl{$c$}: |
226 \underline{language}\\ wrt to a character \bl{$c$}: |
227 \bigskip |
227 \bigskip |
228 |
228 |
229 \begin{center} |
229 \begin{center} |
230 \bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
230 \bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
231 \end{center}\bigskip\bigskip |
231 \end{center}\bigskip\bigskip\bigskip3 |
232 |
232 |
233 For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then |
233 For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then |
234 |
234 |
235 \begin{center} |
235 \begin{center} |
236 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
236 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
559 |
559 |
560 \begin{enumerate} |
560 \begin{enumerate} |
561 \item \bl{$Der\,a\,(L(r_1))$}\pause |
561 \item \bl{$Der\,a\,(L(r_1))$}\pause |
562 \item \bl{$Der\,b\,(Der\,a\,(L(r_1)))$}\pause |
562 \item \bl{$Der\,b\,(Der\,a\,(L(r_1)))$}\pause |
563 \item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r_1))))$}\bigskip |
563 \item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r_1))))$}\bigskip |
564 \item finally we test whether the empty string is in this set\medskip |
564 \item finally we test whether the empty string is in this |
|
565 set; same for \bl{$Ders\,abc\,(L(r_1))$}.\medskip |
565 \end{enumerate} |
566 \end{enumerate} |
566 |
567 |
567 The matching algorithm works similarly, just over regular expressions instead of sets. |
568 The matching algorithm works similarly, just over regular expressions instead of sets. |
568 \end{frame} |
569 \end{frame} |
569 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
570 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
634 What happens if we extend our regular expressions |
635 What happens if we extend our regular expressions |
635 |
636 |
636 \begin{center} |
637 \begin{center} |
637 \begin{tabular}{rcl} |
638 \begin{tabular}{rcl} |
638 \bl{$r$} & \bl{$::=$} & \bl{\ldots}\\ |
639 \bl{$r$} & \bl{$::=$} & \bl{\ldots}\\ |
639 & \bl{$\mid$} & \bl{$r\{n\}$}\\ |
640 & \bl{$\mid$} & \bl{$r^{\{n\}}$}\\ |
640 & \bl{$\mid$} & \bl{$r?$} |
641 & \bl{$\mid$} & \bl{$r?$} |
641 \end{tabular} |
642 \end{tabular} |
642 \end{center} |
643 \end{center} |
643 |
644 |
644 What is their meaning? What are the cases for \bl{$nullable$} and \bl{$der$}? |
645 What is their meaning? What are the cases for \bl{$nullable$} and \bl{$der$}? |
732 \end{frame} |
733 \end{frame} |
733 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
734 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
734 |
735 |
735 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
736 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
736 \begin{frame}[t] |
737 \begin{frame}[t] |
|
738 \frametitle{What is good about this Alg.} |
|
739 |
|
740 \begin{itemize} |
|
741 \item extends to most regular expressions, for example |
|
742 \bl{$\sim r$} |
|
743 |
|
744 \item is easy to implement in a functional language |
|
745 |
|
746 \item the algorithm is already quite old; there is still |
|
747 work to be done to use it as a tokenizer (that is brand new work) |
|
748 |
|
749 \item we can prove its correctness\ldots |
|
750 \end{itemize} |
|
751 |
|
752 \end{frame} |
|
753 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
754 |
|
755 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
756 \begin{frame}[t] |
737 \frametitle{Proofs about Rexps} |
757 \frametitle{Proofs about Rexps} |
738 |
758 |
739 Remember their inductive definition:\\[5cm] |
759 Remember their inductive definition:\\[5cm] |
740 |
760 |
741 \begin{textblock}{6}(5,5) |
761 \begin{textblock}{6}(5,5) |