Binary file handouts/ho03.pdf has changed

--- a/handouts/ho03.tex	Thu Oct 17 13:41:30 2019 +0100
+++ b/handouts/ho03.tex	Thu Oct 17 14:02:59 2019 +0100
@@ -1,3 +1,4 @@
+% !TEX program = xelatex
 \documentclass{article}
 \usepackage{../style}
 \usepackage{../langs}
@@ -914,24 +915,23 @@
 Page~\pageref{dfa}).\bigskip
 
 \noindent
-To start remember that we did not bother with defining and
-implementing $\epsilon$NFAs: we immediately translated them into
-equivalent NFAs. Equivalent in the sense of accepting the same
-language (though we only claimed this and did not prove it
-rigorously). Remember also that NFAs have non-deterministic
-transitions defined as a relation or implemented as function returning
-sets of states.  This non-determinism is crucial for the Thompson
-Construction to work (recall the cases for $\cdot$, $+$ and
-${}^*$). But this non-determinism makes it harder with NFAs to decide
-when a string is accepted or not; whereas such a decision is rather
-straightforward with DFAs: recall their transition function is a
-\emph{function} that returns a single state. So with DFAs we do not
-have to search at all.  What is perhaps interesting is the fact that
-for every NFA we can find a DFA that also recognises the same
-language. This might sound a bit paradoxical: NFA $\rightarrow$
-decision of acceptance hard; DFA $\rightarrow$ decision easy. But this
-\emph{is} true\ldots but of course there is always a caveat---nothing
-ever is for free in life.
+To start, remember that we did not bother with defining and implementing
+$\epsilon$NFAs: we immediately translated them into equivalent NFAs.
+Equivalent in the sense of accepting the same language (though we only
+claimed this and did not prove it rigorously). Remember also that NFAs
+have non-deterministic transitions defined as a relation, or
+alternatively my Scala implementation used transition functions returning sets of
+states.  This non-determinism is crucial for the Thompson Construction
+to work (recall the cases for $\cdot$, $+$ and ${}^*$). But this
+non-determinism makes it harder with NFAs to decide when a string is
+accepted or not; whereas such a decision is rather straightforward with
+DFAs: recall their transition function is a ``real'' function that returns
+a single state. So with DFAs we do not have to search at all.  What is
+perhaps interesting is the fact that for every NFA we can find a DFA
+that also recognises the same language. This might sound a bit
+paradoxical: NFA $\rightarrow$ decision of acceptance hard; DFA
+$\rightarrow$ decision easy. But this \emph{is} true\ldots but of course
+there is always a caveat---nothing ever is for free in life.
 
 There are actually a number of methods for transforming a NFA into
 an equivalent DFA, but the most famous one is the \emph{subset

Binary file slides/slides03.pdf has changed

--- a/slides/slides03.tex	Thu Oct 17 13:41:30 2019 +0100
+++ b/slides/slides03.tex	Thu Oct 17 14:02:59 2019 +0100
@@ -784,7 +784,7 @@
 \frametitle{Subset Construction}
 
 
-\begin{textblock}{5}(1,1)
+\begin{textblock}{5}(1,1.5)
 \begin{center}
 \begin{tikzpicture}[node distance=6mm,scale=0.7,>=stealth',very thick,
                              every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]

Binary file slides/slides04.pdf has changed

--- a/slides/slides04.tex	Thu Oct 17 13:41:30 2019 +0100
+++ b/slides/slides04.tex	Thu Oct 17 14:02:59 2019 +0100
@@ -487,7 +487,7 @@
 In programming languages they are often used to recognise:\medskip
 
 \begin{itemize}
-\item symbols, digits
+\item operands, digits
 \item identifiers
 \item numbers (non-leading zeros)
 \item keywords
@@ -616,9 +616,9 @@
 \bl{(ab + a) \cdot (c + bc)}
 \]\medskip
 
-and the string $\bl{abc}$.\pause\pause\bigskip
+and the string $\bl{abc}$.\pause\bigskip
 
-Or, keywords are \pcode{if} and identifiers are 
+Or, keywords are \code{if} etc and identifiers are 
 letters followed by ``letters + numbers + \_''$^*$
 
 \[
@@ -741,48 +741,6 @@
 
 \end{frame}
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Mkeps}
-
-Finding a (posix) value for recognising the empty string:
-
-\begin{center}
-\begin{tabular}{lcl}
-  \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))$}\\
-  \bl{$mkeps\,(r_1 \cdot r_2)$}  & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\
-  \bl{$mkeps\,(r^*)$}      & \bl{$\dn$} & \bl{$Stars\,[]$}  \\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Inject}
-
-Injecting (``Adding'') a character to a value\\[-12mm]\mbox{}
-
-\begin{center}
-\begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
-  \bl{$inj\,(c)\,c\,(Empty)$} & \bl{$\dn$}  & \bl{$Char\,c$}\\
-  \bl{$inj\,(r_1 + r_2)\,c\,(Left(v))$} & \bl{$\dn$}  & \bl{$Left(inj\,r_1\,c\,v)$}\\
-  \bl{$inj\,(r_1 + r_2)\,c\,(Right(v))$} & \bl{$\dn$}  & \bl{$Right(inj\,r_2\,c\,v)$}\\
-  \bl{$inj\,(r_1 \cdot r_2)\,c\,(Seq(v_1,v_2))$} & \bl{$\dn$}  & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
-  \bl{$inj\,(r_1 \cdot r_2)\,c\,(Left(Seq(v_1,v_2)))$} & \bl{$\dn$}  & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
-  \bl{$inj\,(r_1 \cdot r_2)\,c\,(Right(v))$} & \bl{$\dn$}  & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
-  \bl{$inj\,(r^*)\,c\,(Seq(v,Stars\,vs))$} & \bl{$\dn$}  & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}\\
-\end{tabular}
-\end{center}\bigskip
-
-\footnotesize
-\bl{$inj$}: 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character; 3rd arg $\mapsto$ a value 
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 
@@ -814,7 +772,7 @@
 \end{tikzpicture}
 \end{textblock}
 
-\only<2->{
+\only<1->{
 \begin{textblock}{6}(1,0.8)
 \begin{bubble}[6cm]
 \small
@@ -930,7 +888,53 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+  \frametitle{Mkeps}
+  
+  Finding a (posix) value for recognising the empty string:
+  
+  \begin{center}
+  \begin{tabular}{lcl}
+    \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))$}\\
+    \bl{$mkeps\,(r_1 \cdot r_2)$}  & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\
+    \bl{$mkeps\,(r^*)$}      & \bl{$\dn$} & \bl{$Stars\,[]$}  \\
+  \end{tabular}
+  \end{center}
+  
+  \end{frame}
+  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+  
+  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+  \begin{frame}[c]
+  \frametitle{Inject}
+  
+  Injecting (``Adding'') a character to a value\\[-12mm]\mbox{}
+  
+  \begin{center}
+  \begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
+    \bl{$inj\,(c)\,c\,(Empty)$} & \bl{$\dn$}  & \bl{$Char\,c$}\\
+    \bl{$inj\,(r_1 + r_2)\,c\,(Left(v))$} & \bl{$\dn$}  & \bl{$Left(inj\,r_1\,c\,v)$}\\
+    \bl{$inj\,(r_1 + r_2)\,c\,(Right(v))$} & \bl{$\dn$}  & \bl{$Right(inj\,r_2\,c\,v)$}\\
+    \bl{$inj\,(r_1 \cdot r_2)\,c\,(Seq(v_1,v_2))$} & \bl{$\dn$}  & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
+    \bl{$inj\,(r_1 \cdot r_2)\,c\,(Left(Seq(v_1,v_2)))$} & \bl{$\dn$}  & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
+    \bl{$inj\,(r_1 \cdot r_2)\,c\,(Right(v))$} & \bl{$\dn$}  & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
+    \bl{$inj\,(r^*)\,c\,(Seq(v,Stars\,vs))$} & \bl{$\dn$}  & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}\\
+  \end{tabular}
+  \end{center}\bigskip
+  
+  \footnotesize
+  \begin{tabular}{l@{\hspace{2mm}}l}
+  \bl{$inj$}: & 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character; 
+  3rd arg $\mapsto$ a value\\
+              & result $\mapsto$ a value 
+  \end{tabular}
+  \end{frame}
+  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+  
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Lexing}