diff -r e0492fe3d10b -r c7d4ee344451 slides/slides02.tex --- a/slides/slides02.tex Sat Sep 24 08:47:25 2016 +0100 +++ b/slides/slides02.tex Sat Oct 01 22:30:51 2016 +0100 @@ -144,7 +144,7 @@ \begin{center} \begin{tabular}{lcl} -\bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ +\bl{$A^0$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ \bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$} \end{tabular} \end{center}\bigskip @@ -152,9 +152,10 @@ \item[] For example \begin{center} -\begin{tabular}{l} -\bl{$A^4 = A \,@\, A \,@\, A \,@\, A$}\\ -\bl{$A^0 \dn \{[]\}$}\\ +\begin{tabular}{lcl} +\bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$}\\ +\bl{$A^1$} & \bl{$=$} & \bl{$A$}\\ +\bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ \end{tabular} \end{center} @@ -196,7 +197,7 @@ \begin{center} \begin{tabular}{c} -\bl{$A^* \dn \bigcup_{0\le n} A^n$} +\bl{$A\star \dn \bigcup_{0\le n} A^n$} \end{tabular} \end{center}\bigskip @@ -291,7 +292,7 @@ \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ - \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))^*$}\\ + \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star$}\\ \end{tabular} \end{textblock} @@ -403,7 +404,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}} +\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}} \begin{center} \begin{tikzpicture} @@ -442,7 +443,7 @@ \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip \item Evil regular expressions\medskip \begin{itemize} -\item \bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$} +\item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$} \item \bl{$(a^+)^+$} \item \bl{$([a$\,-\,$z]^+)^*$} \item \bl{$(a + a \cdot a)^+$} @@ -528,6 +529,20 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{The Algorithm} + +\begin{center} +\begin{tabular}{l} +\bl{$\textit{matches}\,r\,s \dn \textit{nullable}(\textit{ders}\,r\,s)$} +\end{tabular} +\end{center} + + +\end{frame} +%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] \frametitle{The Algorithm} @@ -572,7 +587,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}} +\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}} \begin{center} \begin{tikzpicture} @@ -649,7 +664,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] -\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}} +\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}} \begin{center} \begin{tikzpicture} @@ -707,7 +722,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] -\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}} +\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}} \begin{center} \begin{tikzpicture}