
diff -r a47c4227a0c6 -r 7e71c947ec69 slides/slides02.tex
--- 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)$\\




