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\bigskip3 |
231 \end{center}\bigskip\bigskip\bigskip |
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} |
401 \end{frame} |
401 \end{frame} |
402 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
402 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
403 |
403 |
404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
405 \begin{frame}[c] |
405 \begin{frame}[c] |
406 \frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}} |
406 \frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}} |
407 |
407 |
408 \begin{center} |
408 \begin{center} |
409 \begin{tikzpicture} |
409 \begin{tikzpicture} |
410 \begin{axis}[ |
410 \begin{axis}[ |
411 xlabel={\pcode{a}s}, |
411 xlabel={\pcode{a}s}, |
440 |
440 |
441 \begin{itemize} |
441 \begin{itemize} |
442 \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip |
442 \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip |
443 \item Evil regular expressions\medskip |
443 \item Evil regular expressions\medskip |
444 \begin{itemize} |
444 \begin{itemize} |
445 \item \bl{$(a?\{n\}) \cdot a\{n\}$} |
445 \item \bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$} |
446 \item \bl{$(a^+)^+$} |
446 \item \bl{$(a^+)^+$} |
447 \item \bl{$([a$\,-\,$z]^+)^*$} |
447 \item \bl{$([a$\,-\,$z]^+)^*$} |
448 \item \bl{$(a + a \cdot a)^+$} |
448 \item \bl{$(a + a \cdot a)^+$} |
449 \item \bl{$(a + a?)^+$} |
449 \item \bl{$(a + a?)^+$} |
450 \end{itemize} |
450 \end{itemize} |
570 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
570 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
571 |
571 |
572 |
572 |
573 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
573 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
574 \begin{frame}[c] |
574 \begin{frame}[c] |
575 \frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}} |
575 \frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}} |
576 |
576 |
577 \begin{center} |
577 \begin{center} |
578 \begin{tikzpicture} |
578 \begin{tikzpicture} |
579 \begin{axis}[ |
579 \begin{axis}[ |
580 xlabel={\pcode{a}s}, |
580 xlabel={\pcode{a}s}, |
606 |
606 |
607 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
607 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
608 \begin{frame}[c] |
608 \begin{frame}[c] |
609 \frametitle{A Problem} |
609 \frametitle{A Problem} |
610 |
610 |
611 We represented the ``n-times'' \bl{$a\{n\}$} as a |
611 We represented the ``n-times'' \bl{$a^{\{n\}}$} as a |
612 sequence regular expression: |
612 sequence regular expression: |
613 |
613 |
614 \begin{center} |
614 \begin{center} |
615 \begin{tabular}{rl} |
615 \begin{tabular}{rl} |
616 1: & \bl{$a$}\\ |
616 1: & \bl{$a$}\\ |
621 & \ldots\\ |
621 & \ldots\\ |
622 20: |
622 20: |
623 \end{tabular} |
623 \end{tabular} |
624 \end{center} |
624 \end{center} |
625 |
625 |
626 This problem is aggravated with \bl{$a?$} being represented |
626 This problem is aggravated with \bl{$a^?$} being represented |
627 as \bl{$\epsilon + a$}. |
627 as \bl{$\epsilon + a$}. |
628 \end{frame} |
628 \end{frame} |
629 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
629 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
630 |
630 |
631 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
631 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
636 |
636 |
637 \begin{center} |
637 \begin{center} |
638 \begin{tabular}{rcl} |
638 \begin{tabular}{rcl} |
639 \bl{$r$} & \bl{$::=$} & \bl{\ldots}\\ |
639 \bl{$r$} & \bl{$::=$} & \bl{\ldots}\\ |
640 & \bl{$\mid$} & \bl{$r^{\{n\}}$}\\ |
640 & \bl{$\mid$} & \bl{$r^{\{n\}}$}\\ |
641 & \bl{$\mid$} & \bl{$r?$} |
641 & \bl{$\mid$} & \bl{$r^?$} |
642 \end{tabular} |
642 \end{tabular} |
643 \end{center} |
643 \end{center} |
644 |
644 |
645 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$}? |
646 \end{frame} |
646 \end{frame} |
647 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
647 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
648 |
648 |
649 |
649 |
650 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
650 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
651 \begin{frame}[t] |
651 \begin{frame}[t] |
652 \frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}} |
652 \frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}} |
653 |
653 |
654 \begin{center} |
654 \begin{center} |
655 \begin{tikzpicture} |
655 \begin{tikzpicture} |
656 \begin{axis}[ |
656 \begin{axis}[ |
657 xlabel={\pcode{a}s}, |
657 xlabel={\pcode{a}s}, |
705 |
705 |
706 |
706 |
707 |
707 |
708 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
708 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
709 \begin{frame}[t] |
709 \begin{frame}[t] |
710 \frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}} |
710 \frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}} |
711 |
711 |
712 \begin{center} |
712 \begin{center} |
713 \begin{tikzpicture} |
713 \begin{tikzpicture} |
714 \begin{axis}[ |
714 \begin{axis}[ |
715 xlabel={\pcode{a}s}, |
715 xlabel={\pcode{a}s}, |
909 |
909 |
910 |
910 |
911 We can finally prove |
911 We can finally prove |
912 |
912 |
913 \begin{center} |
913 \begin{center} |
914 \bl{$matches(r, s)$} if and only if \bl{$s \in L(r)$} |
914 \bl{$matches\,s\,r$} if and only if \bl{$s \in L(r)$} |
915 \end{center} |
915 \end{center} |
916 |
916 |
917 |
917 |
918 \end{frame} |
918 \end{frame} |
919 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
919 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |