Binary file coursework/cw02.pdf has changed

--- a/coursework/cw02.tex	Sat Oct 13 13:51:28 2018 +0100
+++ b/coursework/cw02.tex	Tue Oct 16 00:42:10 2018 +0100
@@ -172,18 +172,18 @@
 after each derivation step and rectify the computed values after each
 injection. Use this lexer to tokenize the programs in
 Figure~\ref{fib} and \ref{loop}. Give the tokens of these
-programs where whitespaces are filtered out.
+programs where whitespaces are filtered out.\bigskip
 
 
-\begin{figure}[p]
-\mbox{\lstinputlisting[language=while]{../progs/fib.while}}
+\begin{figure}[h]
+\mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../progs/fib.while}}
 \caption{Fibonacci program in the WHILE language.\label{fib}}
 \end{figure}
 
-\begin{figure}[p]
-\mbox{\lstinputlisting[language=while]{../progs/loops.while}}
+\begin{figure}[h]
+\mbox{\lstinputlisting[language=While,xleftmargin=10mm]{../progs/loops.while}}
 \caption{The three-nested-loops program in the WHILE language. 
-Usually used for timing measurements.\label{loop}}
+(Usually used for timing measurements.)\label{loop}}
 \end{figure}
 
 \end{document}

Binary file handouts/ho03.pdf has changed

--- a/handouts/ho03.tex	Sat Oct 13 13:51:28 2018 +0100
+++ b/handouts/ho03.tex	Tue Oct 16 00:42:10 2018 +0100
@@ -1355,15 +1355,15 @@
 \end{eqnarray}
  
 \noindent Unfortunately we cannot make any more progress with
-substituting equations, because both (6) and (7) contain the
+substituting equations, because both (8) and (9) contain the
 variable on the left-hand side also on the right-hand side.
 Here we need to now use a law that is different from the usual
 laws about linear equations. It is called \emph{Arden's rule}.
 It states that if an equation is of the form $q = q\,r + s$
 then it can be transformed to $q = s\, r^*$. Since we can
-assume $+$ is symmetric, Equation (7) is of that form: $s$ is
+assume $+$ is symmetric, Equation (9) is of that form: $s$ is
 $Q_0\,a\,a$ and $r$ is $a$. That means we can transform
-(7) to obtain the two new equations
+(9) to obtain the two new equations
 
 \begin{eqnarray}
 Q_0 & = & \ONE + Q_0\,(b + a\,b) +  Q_2\,b\\

Binary file pics/s1.png has changed

Binary file pics/s2.png has changed

Binary file pics/s3.png has changed

Binary file pics/s4.png has changed

Binary file pics/stickman.jpg has changed

Binary file slides/slides04.pdf has changed

--- a/slides/slides04.tex	Sat Oct 13 13:51:28 2018 +0100
+++ b/slides/slides04.tex	Tue Oct 16 00:42:10 2018 +0100
@@ -27,28 +27,164 @@
   \begin{center}
   \begin{tabular}{ll}
   Email:  & christian.urban at kcl.ac.uk\\
-  Office: & N7.07 (North Wing, Bush House)\\
-  Slides: & KEATS (also home work is there)\\
+  Office: & N\liningnums{7.07} (North Wing, Bush House)\\
+  Slides: & KEATS (also homework is there)\\
   \end{tabular}
   \end{center}
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Survey: Thanks!}
+\small
+
+\hspace{9mm}{\it``\ldots Thanks a million! Thanks without end!''}
+
+\begin{textblock}{3}(12,1.7)
+\includegraphics[scale=0.1]{../pics/stickman.jpg}
+\end{textblock}\pause
+
+\begin{textblock}{6}(1,4.15)
+\begin{bubble}[6.7cm]
+  \it ``Urban is a very talented lecturer: thorough, concise,
+  clear, and cares to make sure that we are learning!''
+\end{bubble}
+\end{textblock}
+
+\only<3>{
+\begin{textblock}{6}(0.6,8.5)
+\includegraphics[scale=0.2]{../pics/s1.png}
+\end{textblock}
+\begin{textblock}{6}(8,8.5)
+\includegraphics[scale=0.2]{../pics/s2.png}
+\end{textblock}}
+
+\only<4>{
+\begin{textblock}{6}(0.6,8.5)
+\includegraphics[scale=0.2]{../pics/s3.png}
+\end{textblock}
+\begin{textblock}{6}(8,8.5)
+\includegraphics[scale=0.2]{../pics/s4.png}
+\end{textblock}}  
+
+% \begin{itemize}
+% \item {\bf My Voice} ``lecturer speaks in a low voice and 
+%   is hard to hear him'' ``please use mic'' ``please use mic 
+%   \& lecture recording''
+% \item {\bf Pace} ``faster pace'' ``a bit quick for me 
+% personally''
+% \item {\bf Recording} ``please use recording class''
+% \item {\bf Module Name} ``misleading''
+% \item {\bf Examples} ``more examples''
+% \item {\bf Assessment} ``really appreciate extension of 
+%   first coursework'' 
+% \end{itemize}
+  
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Regular Expressions}
 
-In programming languages they are often used to recognise:\medskip
+\begin{center}
+\begin{tikzpicture}[scale=2,>=stealth',very thick,
+                             every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
+  \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};}
+  \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};}                           
+  \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};}
+  \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};}
+  \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$};
+  \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
+                  (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
+                  (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
+                  (q1) edge node[above] {\alert{$a$}} (q2)
+                  (q2) edge [loop right] node {\alert{$a$}} ()
+                  (q0) edge [loop below] node {\alert{$b$}} ()
+            ;
+\end{tikzpicture}
+\end{center}\bigskip
 
-\begin{itemize}
-\item symbols, digits
-\item identifiers
-\item numbers (non-leading zeros)
-\item keywords
-\item comments
-\end{itemize}\bigskip
+\begin{center}
+\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b +  \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\
+\end{tabular}
+\end{center}
+
+
+Arden's Lemma:
+\begin{center}
+If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
+\end{center}
+
+\only<2-6>{\small
+\begin{textblock}{6}(1,0.8)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+\multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} + \bl{$\mbox{Q}_2$}:}\\    
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b +  \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<3-6>{\small
+\begin{textblock}{6}(2,4.15)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+\multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\    
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
+\end{tabular}
+\end{bubble}
+\end{textblock}}
 
-\mbox{}\hfill\bl{\url{http://www.regexper.com}}
+\only<4-6>{\small
+\begin{textblock}{6}(3,7.55)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+  \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\    
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$}
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<5-6>{\small
+\begin{textblock}{6}(4,10.9)
+\begin{bubble}[7.5cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+  \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\    
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<6>{\small
+\begin{textblock}{6}(5,13.4)
+\begin{bubble}[7.5cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+  \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\    
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+
+\only<7->{\small
+\begin{textblock}{6}(6,11.5)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+\multicolumn{3}{@{}l}{Finally:}\\    
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\
+\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -98,10 +234,12 @@
     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[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data};	 
 \end{axis}
 \end{tikzpicture}
 
+The punchline is that existing libraries do depth-first search in NFAs.
+
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -261,6 +399,7 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+  
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -305,7 +444,7 @@
                       minimum height=18mm, minimum width=20mm,
                       top color=white,bottom color=black!20}]
 
-  \node at (3.05, 1.8) {\Large\bf Write A Compiler};
+  \node at (3.05, 1.8) {\Large\bf Write a compiler};
 
   \node (0) at (-2.3,0) {}; 
   
@@ -335,24 +474,21 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Survey: Thanks!}
-\small
+\frametitle{Regular Expressions}
+
+In programming languages they are often used to recognise:\medskip
 
-% \begin{itemize}
-% \item {\bf My Voice} ``lecturer speaks in a low voice and 
-%   is hard to hear him'' ``please use mic'' ``please use mic 
-%   \& lecture recording''
-% \item {\bf Pace} ``faster pace'' ``a bit quick for me 
-% personally''
-% \item {\bf Recording} ``please use recording class''
-% \item {\bf Module Name} ``misleading''
-% \item {\bf Examples} ``more examples''
-% \item {\bf Assessment} ``really appreciate extension of 
-%   first coursework'' 
-% \end{itemize}
-  
+\begin{itemize}
+\item symbols, digits
+\item identifiers
+\item numbers (non-leading zeros)
+\item keywords
+\item comments
+\end{itemize}\bigskip
+
+\mbox{}\hfill\bl{\url{http://www.regexper.com}}
 \end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -364,13 +500,13 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{?? Test Case}
-
-\mbox{\lstinputlisting[language=While]{../progs/collatz.while}}
-
-\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+%\begin{frame}[c]
+%\frametitle{?? Test Case}
+%
+%\mbox{\lstinputlisting[language=While]{../progs/collatz.while}}
+%
+%\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -444,7 +580,7 @@
 
 
 There is one small problem with the tokenizer. How should we 
-tokenize:
+tokenize\ldots?
 
 \begin{center}
 \large\code{"x-3"}
@@ -478,7 +614,7 @@
 letters followed by ``letters + numbers + \_''$^*$
 
 \[
-\bl{iffoo}
+\bl{if}\qquad\bl{iffoo}
 \]
 
 \end{frame}
@@ -576,8 +712,8 @@
            & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\
            & \bl{$\mid$} & \bl{$Left(v)$}   \\
            & \bl{$\mid$} & \bl{$Right(v)$}  \\
-           & \bl{$\mid$} & \bl{$[]$}      \\
-           & \bl{$\mid$} & \bl{$[v_1,\ldots\,v_n]$} \\
+           & \bl{$\mid$} & \bl{$Stars\,[]$}      \\
+           & \bl{$\mid$} & \bl{$Stars\,[v_1,\ldots\,v_n]$} \\
   \end{tabular}
 \end{column}
 \end{columns}
@@ -610,7 +746,7 @@
                           &             & \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{$[]$}  \\
+  \bl{$mkeps\,(r^*)$}      & \bl{$\dn$} & \bl{$Stars\,[]$}  \\
 \end{tabular}
 \end{center}
 
@@ -624,14 +760,14 @@
 Injecting (``Adding'') a character to a value\\[-12mm]\mbox{}
 
 \begin{center}
-\begin{tabular}{@{}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,vs)$} & \bl{$\dn$}  & \bl{$inj\,r\,c\,v\,::\,vs$}\\
+\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,vs))$} & \bl{$\dn$}  & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}\\
 \end{tabular}
 \end{center}\bigskip
 
@@ -909,7 +1045,7 @@
 
 \begin{itemize}
 \item If we simplify after the derivative, then we are building the
-value for the simplified regular expression, but \emph{not} for the original
+value for the simplified regular expression, but \alert{\textbf{not}} for the original
 regular expression.
 \end{itemize}
 
@@ -956,12 +1092,13 @@
   \end{center}
 
   and answer how this regular expression matches the empty string
+  with the value
 
   \begin{center}
   \bl{$Right(Right(Empty))$}
   \end{center}\bigskip
 
-  But now we simplify this to \bl{$\ONE$} and would produce \bl{$Empty$}.
+  But now we simplify this to \bl{$\ONE$} and would produce \bl{$Empty$} (see \textit{mkeps}).
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
@@ -1199,7 +1336,7 @@
   \bl{$env(Left(v))$}   & \bl{$\dn$} & \bl{$env(v)$}\\
   \bl{$env(Right(v))$}  & \bl{$\dn$} & \bl{$env(v)$}\\
   \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\
-  \bl{$env([v_1,\ldots ,v_n])$} & \bl{$\dn$} & 
+  \bl{$env(Stars\,[v_1,\ldots ,v_n])$} & \bl{$\dn$} & 
      \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\
   \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\
 \end{tabular}
@@ -1301,8 +1438,8 @@
 \begin{frame}[c]
 \begin{center}
 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
-\bl{$zeroable(\varnothing)$}      & \bl{$\dn$} & \bl{$true$}\\
-\bl{$zeroable(\epsilon)$}         & \bl{$\dn$} & \bl{$\textit{false}$}\\
+\bl{$zeroable(\ZERO)$}      & \bl{$\dn$} & \bl{$true$}\\
+\bl{$zeroable(\ONE)$}         & \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)$}\\