afl-material: comparison slides/slides02.tex

equal deleted inserted replaced

-:a47c4227a0c6
+:7e71c947ec69
 \pgfplotsset{compat=1.12}
 \newcommand{\bl}[1]{\textcolor{blue}{#1}}
 % beamer stuff
-\renewcommand{\slidecaption}{AFL 02, King's College London}
+\renewcommand{\slidecaption}{CFL 02, King's College London}
 \begin{document}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 \frametitle{%
 \begin{tabular}{@ {}c@ {}}
 \\[-3mm]
-\LARGE Automata and \\[-2mm]
+\LARGE Compilers and \\[-1mm]
 \LARGE Formal Languages (2)\\[3mm]
 \end{tabular}}
 \normalsize
 \begin{center}
 \begin{center}
 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l}
 $Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\
 $Der\,b\,A$ & $=$ &  $\{\textit{ar}\}$\\
-$Der\,a\,A$ & $=$ & $\varnothing$\\\pause
+$Der\,a\,A$ & $=$ & $\{\}$\\\pause
 \end{tabular}}
 \end{center}
 \small
 We can extend this definition to strings
 Their inductive definition:
 \begin{textblock}{6}(2,7.5)
 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
-\bl{$r$} & \bl{$::=$}  & \bl{$\varnothing$}  & null\\
+\bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & null\\
-& \bl{$\mid$} & \bl{$\epsilon$}       & empty string / \pcode{""} / $[]$\\
+& \bl{$\mid$} & \bl{$\ONE$}       & empty string / \pcode{""} / $[]$\\
 & \bl{$\mid$} & \bl{$c$}              & character\\
 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}  & sequence\\
 & \bl{$\mid$} & \bl{$r_1 + r_2$}      & alternative / choice\\
 & \bl{$\mid$} & \bl{$r^*$}            & star (zero or more)\\
 \end{tabular}
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}}
 \begin{textblock}{15}(1,4)
 \begin{tabular}{@ {}rcl}
-\bl{$L(\varnothing)$}     & \bl{$\dn$} & \bl{$\varnothing$}\\
+\bl{$L(\ZERO)$}     & \bl{$\dn$} & \bl{$\{\}$}\\
-\bl{$L(\epsilon)$}        & \bl{$\dn$} & \bl{$\{[]\}$}\\
+\bl{$L(\ONE)$}        & \bl{$\dn$} & \bl{$\{[]\}$}\\
 \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))^*$}\\
 \end{tabular}
 \begin{frame}[t]
 \frametitle{Corner Cases}
 \begin{center}
 \bl{\begin{tabular}{rcl}
-$a \cdot \varnothing$ & $\not\equiv$ & $a$\\
+$a \cdot \ZERO$ & $\not\equiv$ & $a$\\
-$a + \epsilon$ & $\not\equiv$ & $a$\\
+$a + \ONE$ & $\not\equiv$ & $a$\\
-$\epsilon$ & $\equiv$ & $\varnothing^*$\\
+$\ONE$ & $\equiv$ & $\ZERO^*$\\
-$\epsilon^*$ & $\equiv$ & $\epsilon$\\
+$\ONE^*$ & $\equiv$ & $\ONE$\\
-$\varnothing^*$ & $\not\equiv$ & $\varnothing$\\
+$\ZERO^*$ & $\not\equiv$ & $\ZERO$\\
 \end{tabular}}
 \end{center}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 \frametitle{Simplification Rules}
 \begin{center}
 \bl{\begin{tabular}{rcl}
-$r + \varnothing$  & $\equiv$ & $r$\\
+$r + \ZERO$  & $\equiv$ & $r$\\
-$\varnothing + r$  & $\equiv$ & $r$\\
+$\ZERO + r$  & $\equiv$ & $r$\\
-$r \cdot \epsilon$ & $\equiv$ & $r$\\
+$r \cdot \ONE$ & $\equiv$ & $r$\\
-$\epsilon \cdot r$     & $\equiv$ & $r$\\
+$\ONE \cdot r$     & $\equiv$ & $r$\\
-$r \cdot \varnothing$ & $\equiv$ & $\varnothing$\\
+$r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\
-$\varnothing \cdot r$ & $\equiv$ & $\varnothing$\\
+$\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\
 $r + r$ & $\equiv$ & $r$
 \end{tabular}}
 \end{center}
 \end{frame}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}}
+\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}}
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
 xlabel={\pcode{a}s},
 \begin{itemize}
 \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)^+$}
 \item \bl{$(a + a?)^+$}
 \end{itemize}
 \ldots{}whether a regular expression can match the empty string:
 \begin{center}
 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
-\bl{$nullable(\varnothing)$}    & \bl{$\dn$} & \bl{\textit{false}}\\
+\bl{$nullable(\ZERO)$}    & \bl{$\dn$} & \bl{\textit{false}}\\
-\bl{$nullable(\epsilon)$}       & \bl{$\dn$} & \bl{\textit{true}}\\
+\bl{$nullable(\ONE)$}       & \bl{$\dn$} & \bl{\textit{true}}\\
 \bl{$nullable (c)$}             & \bl{$\dn$} & \bl{\textit{false}}\\
 \bl{$nullable (r_1 + r_2)$}     & \bl{$\dn$} & \bl{$nullable(r_1) \vee nullable(r_2)$} \\
 \bl{$nullable (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \wedge nullable(r_2)$} \\
 \bl{$nullable (r^*)$}           & \bl{$\dn$} & \bl{\textit{true}}\\
 \end{tabular}
 \begin{frame}[c]
 \frametitle{The Derivative of a Rexp}
 \begin{center}
 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
-\bl{$der\, c\, (\varnothing)$}      & \bl{$\dn$} & \bl{$\varnothing$} & \\
+\bl{$der\, c\, (\ZERO)$}      & \bl{$\dn$} & \bl{$\ZERO$} & \\
-\bl{$der\, c\, (\epsilon)$}           & \bl{$\dn$} & \bl{$\varnothing$} & \\
+\bl{$der\, c\, (\ONE)$}           & \bl{$\dn$} & \bl{$\ZERO$} & \\
-\bl{$der\, c\, (d)$}                     & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\
+\bl{$der\, c\, (d)$}                     & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\
 \bl{$der\, c\, (r_1 + r_2)$}        & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\
 \bl{$der\, c\, (r_1 \cdot r_2)$}  & \bl{$\dn$}  & \bl{if $nullable (r_1)$}\\
 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\
 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\
 \bl{$der\, c\, (r^*)$}          & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\bigskip\\\pause
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}}
+\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}}
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
 xlabel={\pcode{a}s},
 20:
 \end{tabular}
 \end{center}
 This problem is aggravated with \bl{$a^?$} being represented
-as \bl{$\epsilon + a$}.
+as \bl{$\ONE + a$}.
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
-\frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}}
+\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}}
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
 xlabel={\pcode{a}s},
 Recall the example of \bl{$r \dn ((a \cdot b) + b)^*$} with
 \begin{center}
 \begin{tabular}{l}
-\bl{$der\,a\,r = ((\epsilon \cdot b) + \varnothing) \cdot r$}\\
+\bl{$der\,a\,r = ((\ONE \cdot b) + \ZERO) \cdot r$}\\
-\bl{$der\,b\,r = ((\varnothing \cdot b) + \epsilon)\cdot r$}\\
+\bl{$der\,b\,r = ((\ZERO \cdot b) + \ONE)\cdot r$}\\
-\bl{$der\,c\,r = ((\varnothing \cdot b) + \varnothing)\cdot r$}
+\bl{$der\,c\,r = ((\ZERO \cdot b) + \ZERO)\cdot r$}
 \end{tabular}
 \end{center}
 What are these regular expressions equivalent to?
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
-\frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}}
+\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}}
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
 xlabel={\pcode{a}s},
 Remember their inductive definition:\\[5cm]
 \begin{textblock}{6}(5,5)
 \begin{tabular}{@ {}rrl}
-\bl{$r$} & \bl{$::=$}  & \bl{$\varnothing$}\\
+\bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}\\
-& \bl{$\mid$} & \bl{$\epsilon$}     \\
+& \bl{$\mid$} & \bl{$\ONE$}     \\
 & \bl{$\mid$} & \bl{$c$}            \\
 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
 & \bl{$\mid$} & \bl{$r_1 + r_2$}    \\
 & \bl{$\mid$} & \bl{$r^*$}          \\
 \end{tabular}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Proofs about Rexp (2)}
 \begin{itemize}
-\item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip
+\item \bl{$P$} holds for \bl{$\ZERO$}, \bl{$\ONE$} and \bl{c}\bigskip
 \item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already
 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
 \item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already
 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
 \item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already
 \begin{frame}[c]
 \frametitle{Proofs about Rexp (4)}
 \begin{center}
 \bl{\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}
-$rev(\varnothing)$   & $\dn$ & $\varnothing$\\
+$rev(\ZERO)$   & $\dn$ & $\ZERO$\\
-$rev(\epsilon)$      & $\dn$ & $\epsilon$\\
+$rev(\ONE)$      & $\dn$ & $\ONE$\\
 $rev(c)$             & $\dn$ & $c$\\
 $rev(r_1 + r_2)$     & $\dn$ & $rev(r_1) + rev(r_2)$\\
 $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
 $rev(r^*)$           & $\dn$ & $rev(r)^*$\\
 \end{tabular}}

changeset 429	7e71c947ec69
parent 398	c8ce95067c1a
child 431	c7d4ee344451