--- a/slides/slides02.tex Sat Sep 24 08:31:04 2016 +0100
+++ b/slides/slides02.tex Sat Sep 24 08:37:48 2016 +0100
@@ -17,7 +17,7 @@
\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}
@@ -27,7 +27,7 @@
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
- \LARGE Automata and \\[-2mm]
+ \LARGE Compilers and \\[-1mm]
\LARGE Formal Languages (2)\\[3mm]
\end{tabular}}
@@ -236,7 +236,7 @@
\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}
@@ -260,8 +260,8 @@
\begin{textblock}{6}(2,7.5)
\begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
- \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$} & null\\
- & \bl{$\mid$} & \bl{$\epsilon$} & empty string / \pcode{""} / $[]$\\
+ \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & null\\
+ & \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\\
@@ -286,8 +286,8 @@
\begin{textblock}{15}(1,4)
\begin{tabular}{@ {}rcl}
- \bl{$L(\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$}\\
- \bl{$L(\epsilon)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\
+ \bl{$L(\ZERO)$} & \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)$}\\
@@ -353,11 +353,11 @@
\begin{center}
\bl{\begin{tabular}{rcl}
-$a \cdot \varnothing$ & $\not\equiv$ & $a$\\
-$a + \epsilon$ & $\not\equiv$ & $a$\\
-$\epsilon$ & $\equiv$ & $\varnothing^*$\\
-$\epsilon^*$ & $\equiv$ & $\epsilon$\\
-$\varnothing^*$ & $\not\equiv$ & $\varnothing$\\
+$a \cdot \ZERO$ & $\not\equiv$ & $a$\\
+$a + \ONE$ & $\not\equiv$ & $a$\\
+$\ONE$ & $\equiv$ & $\ZERO^*$\\
+$\ONE^*$ & $\equiv$ & $\ONE$\\
+$\ZERO^*$ & $\not\equiv$ & $\ZERO$\\
\end{tabular}}
\end{center}
@@ -370,12 +370,12 @@
\begin{center}
\bl{\begin{tabular}{rcl}
-$r + \varnothing$ & $\equiv$ & $r$\\
-$\varnothing + r$ & $\equiv$ & $r$\\
-$r \cdot \epsilon$ & $\equiv$ & $r$\\
-$\epsilon \cdot r$ & $\equiv$ & $r$\\
-$r \cdot \varnothing$ & $\equiv$ & $\varnothing$\\
-$\varnothing \cdot r$ & $\equiv$ & $\varnothing$\\
+$r + \ZERO$ & $\equiv$ & $r$\\
+$\ZERO + r$ & $\equiv$ & $r$\\
+$r \cdot \ONE$ & $\equiv$ & $r$\\
+$\ONE \cdot r$ & $\equiv$ & $r$\\
+$r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\
+$\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\
$r + r$ & $\equiv$ & $r$
\end{tabular}}
\end{center}
@@ -403,7 +403,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}}
+\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}}
\begin{center}
\begin{tikzpicture}
@@ -442,7 +442,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)^+$}
@@ -461,8 +461,8 @@
\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(\epsilon)$} & \bl{$\dn$} & \bl{\textit{true}}\\
+\bl{$nullable(\ZERO)$} & \bl{$\dn$} & \bl{\textit{false}}\\
+\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)$} \\
@@ -493,9 +493,9 @@
\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\, (\epsilon)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\
- \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\
+ \bl{$der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
+ \bl{$der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
+ \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$}\\
@@ -572,7 +572,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}}
+\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}}
\begin{center}
\begin{tikzpicture}
@@ -624,7 +624,7 @@
\end{center}
This problem is aggravated with \bl{$a^?$} being represented
-as \bl{$\epsilon + a$}.
+as \bl{$\ONE + a$}.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -649,7 +649,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
-\frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}}
+\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}}
\begin{center}
\begin{tikzpicture}
@@ -692,9 +692,9 @@
\begin{center}
\begin{tabular}{l}
-\bl{$der\,a\,r = ((\epsilon \cdot b) + \varnothing) \cdot r$}\\
-\bl{$der\,b\,r = ((\varnothing \cdot b) + \epsilon)\cdot r$}\\
-\bl{$der\,c\,r = ((\varnothing \cdot b) + \varnothing)\cdot r$}
+\bl{$der\,a\,r = ((\ONE \cdot b) + \ZERO) \cdot r$}\\
+\bl{$der\,b\,r = ((\ZERO \cdot b) + \ONE)\cdot r$}\\
+\bl{$der\,c\,r = ((\ZERO \cdot b) + \ZERO)\cdot r$}
\end{tabular}
\end{center}
@@ -707,7 +707,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
-\frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}}
+\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}}
\begin{center}
\begin{tikzpicture}
@@ -760,8 +760,8 @@
\begin{textblock}{6}(5,5)
\begin{tabular}{@ {}rrl}
- \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$}\\
- & \bl{$\mid$} & \bl{$\epsilon$} \\
+ \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\
+ & \bl{$\mid$} & \bl{$\ONE$} \\
& \bl{$\mid$} & \bl{$c$} \\
& \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
& \bl{$\mid$} & \bl{$r_1 + r_2$} \\
@@ -779,7 +779,7 @@
\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
@@ -810,8 +810,8 @@
\begin{center}
\bl{\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}
-$rev(\varnothing)$ & $\dn$ & $\varnothing$\\
-$rev(\epsilon)$ & $\dn$ & $\epsilon$\\
+$rev(\ZERO)$ & $\dn$ & $\ZERO$\\
+$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)$\\