Binary file coursework/cw01.pdf has changed

--- a/coursework/cw01.tex	Thu Sep 28 19:07:37 2017 +0100
+++ b/coursework/cw01.tex	Tue Oct 03 23:01:06 2017 +0100
@@ -28,6 +28,9 @@
 exception is the Scala code I showed during the lectures or
 uploaded to KEATS, which you can freely use.\bigskip
 
+\noindent
+If you have any questions, please send me an email in \textbf{good}
+time.\bigskip
 
 \subsection*{Task}
 
@@ -100,7 +103,7 @@
 
 
 
-\subsection*{Question 1}
+\subsection*{Question 1 (Unmarked)}
 
 What is your King's email address (you will need it in
 Question 4)?
@@ -259,8 +262,9 @@
 \item \texttt{"/*test/*test*/"}
 \end{enumerate}
 
-\noindent
-Also let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be
+\subsection*{Question 5}
+
+Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be
 $(a^{\{19,19\}}) \cdot (a^?)$.  Decide whether the following three
 strings consisting of $a$s only can be matched by $(r_1^+)^+$.
 Similarly test them with $(r_2^+)^+$. Again answer in all six cases

Binary file handouts/ho02.pdf has changed

--- a/handouts/ho02.tex	Thu Sep 28 19:07:37 2017 +0100
+++ b/handouts/ho02.tex	Tue Oct 03 23:01:06 2017 +0100
@@ -497,9 +497,9 @@
   \lstinputlisting[numbers=left,linebackgroundcolor=
                   {\ifodd\value{lstnumber}\color{capri!3}\fi}]
                   {../progs/app5.scala}
-\caption{A Scala implementation of the \textit{nullable} and 
-  derivative functions. These functions are easy to
-  implement in functional languages. This is because pattern 
+\caption{A Scala implementation of \textit{nullable} and 
+  derivative function. These functions are easy to
+  implement in functional programming languages. This is because pattern 
   matching and recursion allow us to mimic the mathematical
   definitions very closely. Nearly all functional
   programming languages support pattern matching and
@@ -844,7 +844,7 @@
 
 \begin{center}
 \begin{tabular}{r@{\hspace{1mm}}r@{\hspace{1mm}}l@{\hspace{13mm}}l}
-  $r$ & $::=$ &   $\ZERO$         & null language\\
+  $r$ & $::=$ &   $\ZERO$         & nothing\\
         & $\mid$ & $\ONE$           & empty string / \texttt{""} / []\\
         & $\mid$ & $c$                  & single character\\
         & $\mid$ & $r_1 + r_2$          & alternative / choice\\

Binary file slides/slides01.pdf has changed

--- a/slides/slides01.tex	Thu Sep 28 19:07:37 2017 +0100
+++ b/slides/slides01.tex	Tue Oct 03 23:01:06 2017 +0100
@@ -529,7 +529,7 @@
 
 \begin{textblock}{6}(2,7.5)
   \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
-  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & null\\
+  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & nothing\\
          & \bl{$\mid$} & \bl{$\ONE$}       & empty string / \pcode{""} / $[]$\\
          & \bl{$\mid$} & \bl{$c$}                         & character\\
          & \bl{$\mid$} & \bl{$r_1 + r_2$}  & alternative / choice\\

Binary file slides/slides02.pdf has changed

--- a/slides/slides02.tex	Thu Sep 28 19:07:37 2017 +0100
+++ b/slides/slides02.tex	Tue Oct 03 23:01:06 2017 +0100
@@ -104,6 +104,26 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Evil Regular Expressions}
+
+\begin{itemize}
+\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^*)^*$}
+\item \bl{$([a$\,-\,$z]^+)^*$}
+\item \bl{$(a + a \cdot a)^*$}
+\item \bl{$(a + a?)^*$}
+\end{itemize}
+
+\item sometimes also called \alert{catastrophic backtracking}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -143,7 +163,7 @@
 \frametitle{The Power Operation}
 
 \begin{itemize}
-\item The \alert{\bf Power} of a language:
+\item The \alert{\textbf{\boldmath$n$th Power}} of a language:
 
 \begin{center}
 \begin{tabular}{lcl}
@@ -155,9 +175,9 @@
 \item[] For example
 
 \begin{center}
-\begin{tabular}{lcl}
-\bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$}\\
-\bl{$A^1$} & \bl{$=$} & \bl{$A$}\\
+\begin{tabular}{lcll}
+\bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(\{[]\})$}\\
+\bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(\{[]\})$}\\
 \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\
 \end{tabular}
 \end{center}
@@ -244,28 +264,7 @@
 \end{textblock}
 
 \end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Specification\\ of Matching\end{tabular}}
-
-\begin{bubble}[10cm]
-\large
-A regular expression \bl{$r$} matches a string~\bl{$s$} 
-provided
-
-\begin{center}
-\bl{$s \in L(r)$}\\ 
-\end{center}
-\end{bubble}\bigskip\bigskip
-
-\ldots and the point of the this lecture is 
-to decide this problem as fast as possible 
-(unlike Python, Ruby, Java etc)
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -301,6 +300,29 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}The Specification\\ of Matching\end{tabular}}
+
+\begin{bubble}[10cm]
+\large
+A regular expression \bl{$r$} matches a string~\bl{$s$} 
+provided
+
+\begin{center}
+\bl{$s \in L(r)$}\\ 
+\end{center}
+\end{bubble}\bigskip\bigskip
+
+\ldots and the point of the this lecture is 
+to decide this problem as fast as possible 
+(unlike Python, Ruby, Java etc)
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 \frametitle{Regular Expressions}
@@ -397,101 +419,6 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%\newcommand{\YES}{\textcolor{gray}{yes}}
-%\newcommand{\NO}{\textcolor{gray}{no}}
-%\newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}}
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Specification\\[-1mm] for Matching\end{tabular}}
-
-\large
-A regular expression \bl{$r$} matches a string \bl{$s$}\\ if and only if
-
-\begin{center}
-\bl{$s \in L(r)$}\\ 
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$} and \bl{$(a^*)^* \cdot b$}}
-
-\begin{center}\footnotesize
-\begin{tabular}{@{}c@{\hspace{-2mm}}c@{}}
-\begin{tikzpicture}
-\begin{axis}[
-    xlabel={$n$},
-    x label style={at={(1.05,0.0)}},
-    ylabel={time in secs},
-    enlargelimits=false,
-    xtick={0,5,...,30},
-    xmax=33,
-    ymax=35,
-    ytick={0,5,...,30},
-    scaled ticks=false,
-    axis lines=left,
-    width=5.5cm,
-    height=4.5cm, 
-    legend entries={Python,Ruby},  
-    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};  
-\end{axis}
-\end{tikzpicture}
-&
-\begin{tikzpicture}
-\begin{axis}[
-    xlabel={$n$},
-    x label style={at={(1.05,0.0)}},
-    ylabel={time in secs},
-    enlargelimits=false,
-    xtick={0,5,...,30},
-    xmax=33,
-    ymax=35,
-    ytick={0,5,...,30},
-    scaled ticks=false,
-    axis lines=left,
-    width=5.5cm,
-    height=4.5cm, 
-    legend entries={Java},  
-    legend pos=north west,
-    legend cell align=left]
-\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
-\end{axis}
-\end{tikzpicture}
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Evil Regular Expressions}
-
-\begin{itemize}
-\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^*)^*$}
-\item \bl{$([a$\,-\,$z]^+)^*$}
-\item \bl{$(a + a \cdot a)^*$}
-\item \bl{$(a + a?)^*$}
-\end{itemize}
-
-\item sometimes also called \alert{catastrophic backtracking}
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]