diff -r 3056a4c071b0 -r e7d0157f0471 slides/slides04.tex
--- a/slides/slides04.tex	Fri Oct 07 22:08:03 2016 +0100
+++ b/slides/slides04.tex	Sat Oct 08 13:45:30 2016 +0100
@@ -10,7 +10,7 @@
 
 \newcommand{\bl}[1]{\textcolor{blue}{#1}}  
 
-\renewcommand{\slidecaption}{AFL 04, King's College London}
+\renewcommand{\slidecaption}{CFL 04, King's College London}
 
 \begin{document}
 
@@ -19,7 +19,7 @@
 \frametitle{%
   \begin{tabular}{@ {}c@ {}}
   \\[-3mm]
-  \LARGE Automata and \\[-2mm] 
+  \LARGE Compilers and \\[-2mm] 
   \LARGE Formal Languages (4)\\[3mm] 
   \end{tabular}}
 
@@ -61,7 +61,7 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
-\frametitle{\bl{$a^?^{\{n\}} \cdot a^{\{n\}}$}}
+\frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}
 
 \begin{tikzpicture}
 \begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs},
@@ -77,12 +77,9 @@
     legend entries={Python,Ruby,my NFA},  
     legend pos=north west,
     legend cell align=left]
-\addplot[blue,mark=*, mark options={fill=white}] 
-  table {re-python.data};
-\addplot[brown,mark=pentagon*, mark options={fill=white}] 
-  table {re-ruby.data};  
-\addplot[red,mark=triangle*, mark options={fill=white}] 
-  table {nfasearch.data};	  
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
+\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data};  
+\addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data};	  
 \end{axis}
 \end{tikzpicture}
 
@@ -111,7 +108,7 @@
 
 \begin{center}
 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l}
-\bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b +  q_2\,b$} & (start state)\\
+\bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b +  q_2\,b$} & (start state)\\
 \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\
 \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\
 
@@ -241,7 +238,7 @@
 
 
 \small
-for example $a^nb^n$ is not regular
+for example \bl{$a^nb^n$} is not regular
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -542,8 +539,8 @@
 \begin{columns}
 \begin{column}{3cm}
 \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$}   \\
@@ -589,7 +586,7 @@
 
 \begin{center}
 \begin{tabular}{lcl}
-  \bl{$mkeps\,\epsilon$}  & \bl{$\dn$}  & \bl{$Empty$}\\
+  \bl{$mkeps\,\ONE$}  & \bl{$\dn$}  & \bl{$Empty$}\\
   \bl{$mkeps\,r_1 + r_2$} & \bl{$\dn$}  & \bl{if $nullable(r_1)$}  \\
                           &             & \bl{then $Left(mkeps(r_1))$}\\
                           &             & \bl{else $Right(mkeps(r_2))$}\\
@@ -660,9 +657,9 @@
 \small
 \begin{tabular}{ll}
 \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
-\bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\
-\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\
-\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\
+\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\
+\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\
+\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\
 \end{tabular}
 \end{bubble}
 \end{textblock}}
@@ -735,9 +732,9 @@
 \small
 \begin{tabular}{ll}
 \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
-\bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\
-\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\
-\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\
+\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\
+\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\
+\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\
 \end{tabular}
 \end{bubble}
 \end{textblock}
@@ -831,30 +828,12 @@
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Records}
-
-\begin{itemize}
-\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
-
-\item \bl{$nullable(x:r) \dn nullable(r)$}
-\item \bl{$der\,c\,(x:r) \dn (x:der\,c\,r)$}
-\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}
-\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$}
-\end{itemize}\bigskip\bigskip\pause
-
-\small
-for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 
 \begin{itemize}
-\item Regular expression for email addresses
+\item A regular expression for email addresses
 
 \begin{center}
 \begin{tabular}{l}
@@ -868,7 +847,7 @@
 \texttt{christian.urban@kcl.ac.uk}
 \]}
 
-\item result environment:
+\item the result environment:
 
 \begin{center}
 \begin{tabular}{l}
@@ -941,9 +920,9 @@
 \end{center}
 
 \small
-\hspace{4.5cm}\bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}
+\hspace{4.5cm}\bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}
 $\mapsto$
-\bl{$\epsilon$}
+\bl{$\ONE$}
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
@@ -954,22 +933,22 @@
 
 \def\arraystretch{1.05}
 \begin{center}
-\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l@{\hspace{5mm}}l}
+\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l@{\hspace{8mm}}l}
 & & & \hspace{5mm}rectification \\
 & & & \hspace{5mm}functions:\\
-\bl{$r \cdot \varnothing$} & $\mapsto$ & \bl{$\varnothing$} & \\ 
-\bl{$\varnothing \cdot r$} & $\mapsto$ & \bl{$\varnothing$} & \\ 
-\bl{$r \cdot \epsilon$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,v, f_2\,Empty)$}\\ 
-\bl{$\epsilon \cdot r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,Empty, f_2\,v)$}\\ 
-\bl{$r + \varnothing$} & $\mapsto$ & \bl{$r$}   & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$}\\ 
-\bl{$\varnothing + r$} & $\mapsto$ & \bl{$r$}   & \bl{$\lambda f_1\,f_2\,v.\, Right(f_2\,v)$}\\
+\bl{$r \cdot \ZERO$} & $\mapsto$ & \bl{$\ZERO$} & \\ 
+\bl{$\ZERO \cdot r$} & $\mapsto$ & \bl{$\ZERO$} & \\ 
+\bl{$r \cdot \ONE$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,v, f_2\,Empty)$}\\ 
+\bl{$\ONE \cdot r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,Empty, f_2\,v)$}\\ 
+\bl{$r + \ZERO$} & $\mapsto$ & \bl{$r$}   & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$}\\ 
+\bl{$\ZERO + r$} & $\mapsto$ & \bl{$r$}   & \bl{$\lambda f_1\,f_2\,v.\, Right(f_2\,v)$}\\
 \bl{$r + r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$}
 \end{tabular}
 \end{center}\medskip\pause
 
 \small
 old \bl{$simp$} returns a rexp;\\
-new \bl{$simp$} returns a rexp and a rectification~fun.
+new \bl{$simp$} returns a rexp and a rectification~function.
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
@@ -984,9 +963,9 @@
 \quad case \bl{$r = r_1 + r_2$}\\
 \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
 \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
-\qquad case \bl{$r_{1s} = \varnothing$}: 
+\qquad case \bl{$r_{1s} = \ZERO$}: 
        return \bl{$(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$}\\
-\qquad case \bl{$r_{2s} = \varnothing$}: 
+\qquad case \bl{$r_{2s} = \ZERO$}: 
        return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
 \qquad case \bl{$r_{1s} = r_{2s}$}:
        return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
@@ -1010,12 +989,14 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 \begin{frame}[c]
 
 {\footnotesize\lstinputlisting[language=Scala,numbers=none,
 xleftmargin=-5mm] {../progs/app05.scala}}
 
 \end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -1027,13 +1008,13 @@
 \quad case \bl{$r = r_1 \cdot r_2$}\\
 \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
 \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
-\qquad case \bl{$r_{1s} = \varnothing$}: 
-       return \bl{$(\varnothing, f_{error})$}\\
-\qquad case \bl{$r_{2s} = \varnothing$}: 
-       return \bl{$(\varnothing, f_{error})$}\\
-\qquad case \bl{$r_{1s} = \epsilon$}: 
+\qquad case \bl{$r_{1s} = \ZERO$}: 
+       return \bl{$(\ZERO, f_{error})$}\\
+\qquad case \bl{$r_{2s} = \ZERO$}: 
+       return \bl{$(\ZERO, f_{error})$}\\
+\qquad case \bl{$r_{1s} = \ONE$}: 
 return \bl{$(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$}\\
-\qquad case \bl{$r_{2s} = \epsilon$}: 
+\qquad case \bl{$r_{2s} = \ONE$}: 
 return \bl{$(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$}\\
 \qquad otherwise: 
        return \bl{$(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$}\\
@@ -1107,17 +1088,17 @@
 \begin{frame}[c]
 \begin{center}
 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
-$zeroable(\varnothing)$      & $\dn$ & $true$\\
-$zeroable(\epsilon)$           & $\dn$ &  $f\!alse$\\
-$zeroable (c)$                    & $\dn$ &  $f\!alse$\\
-$zeroable (r_1 + r_2)$        & $\dn$ &  $zeroable(r_1) \wedge zeroable(r_2)$ \\ 
-$zeroable (r_1 \cdot r_2)$  & $\dn$ &  $zeroable(r_1) \vee zeroable(r_2)$ \\
-$zeroable (r^*)$                  & $\dn$ & $f\!alse$\\
+\bl{$zeroable(\varnothing)$}      & \bl{$\dn$} & \bl{$true$}\\
+\bl{$zeroable(\epsilon)$}         & \bl{$\dn$} & \bl{$\textit{false}$}\\
+\bl{$zeroable(c)$}                & \bl{$\dn$} & \bl{$\textit{false}$}\\
+\bl{$zeroable(r_1 + r_2)$}        & \bl{$\dn$} & \bl{$zeroable(r_1) \wedge zeroable(r_2)$}\\ 
+\bl{$zeroable(r_1 \cdot r_2)$}    & \bl{$\dn$} & \bl{$zeroable(r_1) \vee zeroable(r_2)$}\\
+\bl{$zeroable(r^*)$}              & \bl{$\dn$} & \bl{$\textit{false}$}\\
 \end{tabular}
 \end{center}
 
 \begin{center}
-$zeroable(r)$ if and only if $L(r) = \varnothing$
+\bl{$zeroable(r)$} if and only if \bl{$L(r) = \{\}$}
 \end{center}