equal
deleted
inserted
replaced
142 \begin{itemize} |
142 \begin{itemize} |
143 \item The \alert{\bf Power} of a language: |
143 \item The \alert{\bf Power} of a language: |
144 |
144 |
145 \begin{center} |
145 \begin{center} |
146 \begin{tabular}{lcl} |
146 \begin{tabular}{lcl} |
147 \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
147 \bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
148 \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} |
148 \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} |
149 \end{tabular} |
149 \end{tabular} |
150 \end{center}\bigskip |
150 \end{center}\bigskip |
151 |
151 |
152 \item[] For example |
152 \item[] For example |
153 |
153 |
154 \begin{center} |
154 \begin{center} |
155 \begin{tabular}{l} |
155 \begin{tabular}{lcl} |
156 \bl{$A^4 = A \,@\, A \,@\, A \,@\, A$}\\ |
156 \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$}\\ |
157 \bl{$A^0 \dn \{[]\}$}\\ |
157 \bl{$A^1$} & \bl{$=$} & \bl{$A$}\\ |
|
158 \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ |
158 \end{tabular} |
159 \end{tabular} |
159 \end{center} |
160 \end{center} |
160 |
161 |
161 \end{itemize} |
162 \end{itemize} |
162 |
163 |
194 \item The \alert{\bf Star} of a \underline{language}: |
195 \item The \alert{\bf Star} of a \underline{language}: |
195 \bigskip |
196 \bigskip |
196 |
197 |
197 \begin{center} |
198 \begin{center} |
198 \begin{tabular}{c} |
199 \begin{tabular}{c} |
199 \bl{$A^* \dn \bigcup_{0\le n} A^n$} |
200 \bl{$A\star \dn \bigcup_{0\le n} A^n$} |
200 \end{tabular} |
201 \end{tabular} |
201 \end{center}\bigskip |
202 \end{center}\bigskip |
202 |
203 |
203 \item[] This expands to |
204 \item[] This expands to |
204 |
205 |
289 \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ |
290 \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ |
290 \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
291 \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
291 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
292 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
292 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
293 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
293 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ |
294 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ |
294 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))^*$}\\ |
295 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star$}\\ |
295 \end{tabular} |
296 \end{tabular} |
296 \end{textblock} |
297 \end{textblock} |
297 |
298 |
298 \begin{textblock}{6}(9,12)\small |
299 \begin{textblock}{6}(9,12)\small |
299 \bl{$L$} is a function from regular expressions to |
300 \bl{$L$} is a function from regular expressions to |
401 \end{frame} |
402 \end{frame} |
402 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
403 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
403 |
404 |
404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
405 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
405 \begin{frame}[c] |
406 \begin{frame}[c] |
406 \frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}} |
407 \frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}} |
407 |
408 |
408 \begin{center} |
409 \begin{center} |
409 \begin{tikzpicture} |
410 \begin{tikzpicture} |
410 \begin{axis}[ |
411 \begin{axis}[ |
411 xlabel={\pcode{a}s}, |
412 xlabel={\pcode{a}s}, |
440 |
441 |
441 \begin{itemize} |
442 \begin{itemize} |
442 \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip |
443 \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip |
443 \item Evil regular expressions\medskip |
444 \item Evil regular expressions\medskip |
444 \begin{itemize} |
445 \begin{itemize} |
445 \item \bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$} |
446 \item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$} |
446 \item \bl{$(a^+)^+$} |
447 \item \bl{$(a^+)^+$} |
447 \item \bl{$([a$\,-\,$z]^+)^*$} |
448 \item \bl{$([a$\,-\,$z]^+)^*$} |
448 \item \bl{$(a + a \cdot a)^+$} |
449 \item \bl{$(a + a \cdot a)^+$} |
449 \item \bl{$(a + a?)^+$} |
450 \item \bl{$(a + a?)^+$} |
450 \end{itemize} |
451 \end{itemize} |
524 \end{tabular} |
525 \end{tabular} |
525 \end{center} |
526 \end{center} |
526 |
527 |
527 \end{frame} |
528 \end{frame} |
528 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
529 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
530 |
|
531 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
532 \begin{frame}[c] |
|
533 \frametitle{The Algorithm} |
|
534 |
|
535 \begin{center} |
|
536 \begin{tabular}{l} |
|
537 \bl{$\textit{matches}\,r\,s \dn \textit{nullable}(\textit{ders}\,r\,s)$} |
|
538 \end{tabular} |
|
539 \end{center} |
|
540 |
|
541 |
|
542 \end{frame} |
|
543 %%%%%%%%%%%%%%%%% |
529 |
544 |
530 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
545 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
531 \begin{frame}[t] |
546 \begin{frame}[t] |
532 \frametitle{The Algorithm} |
547 \frametitle{The Algorithm} |
533 |
548 |
570 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
585 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
571 |
586 |
572 |
587 |
573 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
574 \begin{frame}[c] |
589 \begin{frame}[c] |
575 \frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}} |
590 \frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}} |
576 |
591 |
577 \begin{center} |
592 \begin{center} |
578 \begin{tikzpicture} |
593 \begin{tikzpicture} |
579 \begin{axis}[ |
594 \begin{axis}[ |
580 xlabel={\pcode{a}s}, |
595 xlabel={\pcode{a}s}, |
647 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
662 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
648 |
663 |
649 |
664 |
650 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
665 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
651 \begin{frame}[t] |
666 \begin{frame}[t] |
652 \frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}} |
667 \frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}} |
653 |
668 |
654 \begin{center} |
669 \begin{center} |
655 \begin{tikzpicture} |
670 \begin{tikzpicture} |
656 \begin{axis}[ |
671 \begin{axis}[ |
657 xlabel={\pcode{a}s}, |
672 xlabel={\pcode{a}s}, |
705 |
720 |
706 |
721 |
707 |
722 |
708 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
723 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
709 \begin{frame}[t] |
724 \begin{frame}[t] |
710 \frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}} |
725 \frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}} |
711 |
726 |
712 \begin{center} |
727 \begin{center} |
713 \begin{tikzpicture} |
728 \begin{tikzpicture} |
714 \begin{axis}[ |
729 \begin{axis}[ |
715 xlabel={\pcode{a}s}, |
730 xlabel={\pcode{a}s}, |