
diff -r 15f1fca879c5 -r 94b11ac19b41 cws/cw03.tex
--- a/cws/cw03.tex	Fri Nov 24 09:10:53 2017 +0000
+++ b/cws/cw03.tex	Mon Nov 27 01:15:36 2017 +0000
@@ -110,7 +110,7 @@
 \begin{tabular}{lcll}
   $r$ & $::=$ & $\ZERO$     & cannot match anything\\
       &   $|$ & $\ONE$      & can only match the empty string\\
-      &   $|$ & $c$         & can match a character (in this case $c$)\\
+      &   $|$ & $c$         & can match a single character (in this case $c$)\\
       &   $|$ & $r_1 + r_2$ & can match a string either with $r_1$ or with $r_2$\\
   &   $|$ & $r_1\cdot r_2$ & can match the first part of a string with $r_1$ and\\
           &  & & then the second part with $r_2$\\
@@ -136,11 +136,31 @@
 
 \subsubsection*{Tasks (file re.scala)}
 
+The file \texttt{re.scala} has already a definition for regular
+expressions and also defines some handy shorthand notation for
+regular expressions. The notation in this document matches up
+with the code in the file as follows:
+
+\begin{center}
+  \begin{tabular}{rcl@{\hspace{10mm}}l}
+    & & code: & shorthand:\smallskip \\ 
+  $\ZERO$ & $\mapsto$ & \texttt{ZERO}\\
+  $\ONE$  & $\mapsto$ & \texttt{ONE}\\
+  $c$     & $\mapsto$ & \texttt{CHAR(c)}\\
+  $r_1 + r_2$ & $\mapsto$ & \texttt{ALT(r1, r2)} & \texttt{r1 | r2}\\
+  $r_1 \cdot r_2$ & $\mapsto$ & \texttt{SEQ(r1, r2)} & \texttt{r1 $\sim$ r2}\\
+  $r^*$ & $\mapsto$ &  \texttt{STAR(r)} & \texttt{r.\%}
+\end{tabular}    
+\end{center}  
+
+
 \begin{itemize}
 \item[(1a)] Implement a function, called \textit{nullable}, by
   recursion over regular expressions. This function tests whether a
   regular expression can match the empty string. This means given a
-  regular expression it either returns true or false.
+  regular expression it either returns true or false. The function
+  \textit{nullable}
+  is defined as follows:
 
 \begin{center}
 \begin{tabular}{lcl}
@@ -151,7 +171,7 @@
 $\textit{nullable}(r_1 \cdot r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge \textit{nullable}(r_2)$\\
 $\textit{nullable}(r^*)$ & $\dn$ & $\textit{true}$\\
 \end{tabular}
-\end{center}\hfill[1 Mark]
+\end{center}~\hfill[1 Mark]
 
 \item[(1b)] Implement a function, called \textit{der}, by recursion over
   regular expressions. It takes a character and a regular expression
@@ -314,7 +334,7 @@
 what your matcher is doing.
 
 The purpose of the $\textit{simp}$ function is to keep the regular
-expression small. Normally the derivative function makes the regular
+expressions small. Normally the derivative function makes the regular
 expression bigger (see the SEQ case and the example in (1b)) and the
 algorithm would be slower and slower over time. The $\textit{simp}$
 function counters this increase in size and the result is that the
@@ -328,7 +348,9 @@
 
 
 If you want to see how badly the regular expression matchers do in
-Java\footnote{Version 8 and below} and in Python with the `evil' regular
+Java\footnote{Version 8 and below; Version 9 does not seem to be as
+  catastrophic, but still worse than the regular expression matcher
+based on derivatives.} and in Python with the `evil' regular
 expression $(a^*)^*\cdot b$, then have a look at the graphs below (you
 can try it out for yourself: have a look at the file
 \texttt{catastrophic.java} and \texttt{catastrophic.py} on
@@ -352,7 +374,7 @@
     scaled ticks=false,
     axis lines=left,
     width=6cm,
-    height=5.0cm, 
+    height=5.5cm, 
     legend entries={Python, Java 8},  
     legend pos=outer north east]
 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
@@ -379,7 +401,7 @@
 instructions in total and all of which are single characters. Despite
 the minimalism, this language has been shown to be Turing
 complete\ldots{}if this doesn't ring any bell with you: it roughly
-that means every algorithm we know can, in principle, be implemented in
+means that every algorithm we know can, in principle, be implemented in
 brainf***. It just takes a lot of determination and quite a lot of
 memory resources. Some relatively sophisticated sample programs in
 brainf*** are given in the file \texttt{bf.scala}.\bigskip
@@ -420,20 +442,21 @@
 \item[(2a)] Brainf*** memory is represented by a \texttt{Map} from
   integers to integers. The empty memory is represented by
   \texttt{Map()}, that is nothing is stored in the
-  memory. \texttt{Map(0 -> 1, 2 -> 3)} clearly has stored \texttt{1}
-  at memory location \texttt{0}; at \texttt{2} it stores
-  \texttt{3}. The convention is that if we query the memory at a
-  location that is not defined in the \texttt{Map}, we return
-  \texttt{0}. Write a function, \texttt{sread}, that takes a memory (a
-  \texttt{Map}) and a memory pointer (an \texttt{Int}) as argument,
-  and safely reads the corresponding memory location. If the map is not
-  defined at the memory pointer, \texttt{sread} returns \texttt{0}.
+  memory. \texttt{Map(0 -> 1, 2 -> 3)} clearly stores \texttt{1} at
+  memory location \texttt{0}; at \texttt{2} it stores \texttt{3}. The
+  convention is that if we query the memory at a location that is
+  \emph{not} defined in the \texttt{Map}, we return \texttt{0}. Write
+  a function, \texttt{sread}, that takes a memory (a \texttt{Map}) and
+  a memory pointer (an \texttt{Int}) as argument, and safely reads the
+  corresponding memory location. If the \texttt{Map} is not defined at
+  the memory pointer, \texttt{sread} returns \texttt{0}.
 
   Write another function \texttt{write}, which takes a memory, a
-  memory pointer and an integer value as argument and updates the map
-  with the value at the given memory location. As usual the map is not
-  updated `in-place' but a new map is created with the same data,
-  except the value is stored at the given memory pointer.\hfill[1 Mark]
+  memory pointer and an integer value as argument and updates the
+  \texttt{Map} with the value at the given memory location. As usual
+  the \texttt{Map} is not updated `in-place' but a new map is created
+  with the same data, except the value is stored at the given memory
+  pointer.\hfill[1 Mark]
 
 \item[(2b)] Write two functions, \texttt{jumpRight} and
   \texttt{jumpLeft} that are needed to implement the loop constructs
@@ -454,7 +477,7 @@
   \texttt{--[..+>--]\barbelow{,}>,++}
   \end{center}
 
-  meaning it jumps to after the loop. Similarly, if you in 8th position
+  meaning it jumps to after the loop. Similarly, if you are in 8th position
   then \texttt{jumpLeft} is supposed to jump to just after the opening
   bracket (that is jumping to the beginning of the loop):
 
@@ -552,13 +575,13 @@
       \hfill\texttt{'.'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
                        $\bullet$ & $\texttt{pc} + 1$\\
                        $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
-                       $\bullet$ & print out\texttt{mem(mp)} as a character\\
+                       $\bullet$ & print out \,\texttt{mem(mp)} as a character\\
                      \end{tabular}\\\hline   
       \hfill\texttt{','} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
                        $\bullet$ & $\texttt{pc} + 1$\\
                        $\bullet$ & $\texttt{mp}$ unchanged\\
                        $\bullet$ & \texttt{mem} updated with \texttt{mp -> \textrm{input}}\\
-                       \multicolumn{2}{@{}l}{input given by \texttt{Console.in.read().toByte}}
+                       \multicolumn{2}{@{}l}{the input is given by \texttt{Console.in.read().toByte}}
                      \end{tabular}\\\hline   
       \hfill\texttt{'['} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
                        \multicolumn{2}{@{}l}{if \texttt{mem(mp) == 0} then}\\




