--- 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}