
diff -r 3020f8c76baa -r 9e7897f25e13 cws/cw05.tex
--- a/cws/cw05.tex	Wed Nov 28 23:26:47 2018 +0000
+++ b/cws/cw05.tex	Thu Nov 29 17:15:11 2018 +0000
@@ -1,262 +1,680 @@
 \documentclass{article}
 \usepackage{../style}
 \usepackage{../langs}
-\usepackage{../graphics}
+\usepackage{disclaimer}
+\usepackage{tikz}
+\usepackage{pgf}
+\usepackage{pgfplots}
+\usepackage{stackengine}
+%% \usepackage{accents}
+\newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}}
+
+\begin{filecontents}{re-python2.data}
+1 0.033
+5 0.036
+10 0.034
+15 0.036
+18 0.059
+19 0.084 
+20 0.141
+21 0.248
+22 0.485
+23 0.878
+24 1.71
+25 3.40
+26 7.08
+27 14.12
+28 26.69
+\end{filecontents}
+
+\begin{filecontents}{re-java.data}
+5  0.00298
+10  0.00418
+15  0.00996
+16  0.01710
+17  0.03492
+18  0.03303
+19  0.05084
+20  0.10177
+21  0.19960
+22  0.41159
+23  0.82234
+24  1.70251
+25  3.36112
+26  6.63998
+27  13.35120
+28  29.81185
+\end{filecontents}
+
+\begin{filecontents}{re-js.data}
+5   0.061
+10  0.061
+15  0.061
+20  0.070
+23  0.131
+25  0.308
+26  0.564
+28  1.994
+30  7.648
+31  15.881 
+32  32.190
+\end{filecontents}
+
+\begin{filecontents}{re-java9.data}
+1000  0.01410
+2000  0.04882
+3000  0.10609
+4000  0.17456
+5000  0.27530
+6000  0.41116
+7000  0.53741
+8000  0.70261
+9000  0.93981
+10000 0.97419
+11000 1.28697
+12000 1.51387
+14000 2.07079
+16000 2.69846
+20000 4.41823
+24000 6.46077
+26000 7.64373
+30000 9.99446
+34000 12.966885
+38000 16.281621
+42000 19.180228
+46000 21.984721
+50000 26.950203
+60000 43.0327746
+\end{filecontents}
+
 
 \begin{document}
 
-\section*{Replacement Coursework 2 (Automata)}
+% BF IDE
+% https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5
+  
+\section*{Coursework 9 (Scala)}
 
-This coursework is worth 10\%. It is about deterministic and
-non-deterministic finite automata.  The coursework is due on 21 March
-at 5pm.  Make sure the files you submit can be processed by just
-calling \texttt{scala <<filename.scala>>}.\bigskip
+This coursework is worth 10\%. It is about a regular expression
+matcher and the shunting yard algorithm by Dijkstra. The first part is
+due on 6 December at 11pm; the second, more advanced part, is due on
+21 December at 11pm. In the first part, you are asked to implement a
+regular expression matcher based on derivatives of regular
+expressions. The reason is that regular expression matching in
+languages like Java, JavaScipt and Python can sometimes be extremely
+slow. The advanced part is about the shunting yard algorithm that
+transforms the usual infix notation of arithmetic expressions into the
+postfix notation, which is for example used in compilers.\bigskip
+
+\IMPORTANT{}
 
 \noindent
-\textbf{Important:} Do not use any mutable data structures in your
-submission! They are not needed. This means you cannot use
-\texttt{ListBuffer}s, for example. Do not use \texttt{return} in your
-code! It has a different meaning in Scala, than in Java.  Do not use
-\texttt{var}! This declares a mutable variable.  Make sure the
-functions you submit are defined on the ``top-level'' of Scala, not
-inside a class or object. Also note that when marking, the running time
-will be restricted to a maximum of 360 seconds on my laptop.
+Also note that the running time of each part will be restricted to a
+maximum of 30 seconds on my laptop.
+
+\DISCLAIMER{}
 
 
-\subsection*{Disclaimer}
-
-It should be understood that the work you submit represents your own
-effort! You have not copied from anyone else. An exception is the
-Scala code I showed during the lectures or uploaded to KEATS, which
-you can freely use.\bigskip
-
+\subsection*{Part 1 (6 Marks, Regular Expression Matcher)}
 
-\subsection*{Part 1 (Deterministic Finite Automata)}
-
-\noindent
-There are many uses for Deterministic Finite Automata (DFAs), for
-example for testing whether a string matches a pattern or not.  DFAs
-consist of some states (circles) and some transitions (edges) between
-states. For example the DFA
+The task is to implement a regular expression matcher that is based on
+derivatives of regular expressions. Most of the functions are defined by
+recursion over regular expressions and can be elegantly implemented
+using Scala's pattern-matching. The implementation should deal with the
+following regular expressions, which have been predefined in the file
+\texttt{re.scala}:
 
 \begin{center}
-\begin{tikzpicture}[scale=1.5,>=stealth',very thick,auto,
-                    every state/.style={minimum size=4pt,
-                    inner sep=4pt,draw=blue!50,very thick,
-                    fill=blue!20}]
-  \node[state, initial]        (q0) at ( 0,1) {$Q_0$};
-  \node[state]                    (q1) at ( 1,1) {$Q_1$};
-  \node[state, accepting] (q2) at ( 2,1) {$Q_2$};
-  \path[->] (q0) edge[bend left] node[above] {$a$} (q1)
-            (q1) edge[bend left] node[above] {$b$} (q0)
-            (q2) edge[bend left=50] node[below] {$b$} (q0)
-            (q1) edge node[above] {$a$} (q2)
-            (q2) edge [loop right] node {$a$} ()
-            (q0) edge [loop below] node {$b$} ();
-\end{tikzpicture}
+\begin{tabular}{lcll}
+  $r$ & $::=$ & $\ZERO$     & cannot match anything\\
+      &   $|$ & $\ONE$      & can only match the empty string\\
+      &   $|$ & $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$\\
+      &   $|$ & $r^*$       & can match a string with zero or more copies of $r$\\
+\end{tabular}
 \end{center}
 
-\noindent
-has three states ($Q_0$, $Q_1$ and $Q_2$), whereby $Q_0$ is the
-starting state of the DFA and $Q_2$ is the accepting state. The latter
-is indicated by double lines. In general, a DFA can have any number of
-accepting states, but only a single starting state.
+\noindent 
+Why? Knowing how to match regular expressions and strings will let you
+solve a lot of problems that vex other humans. Regular expressions are
+one of the fastest and simplest ways to match patterns in text, and
+are endlessly useful for searching, editing and analysing data in all
+sorts of places (for example analysing network traffic in order to
+detect security breaches). However, you need to be fast, otherwise you
+will stumble over problems such as recently reported at
+
+{\small
+\begin{itemize}
+\item[$\bullet$] \url{http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}
+\item[$\bullet$] \url{https://vimeo.com/112065252}
+\item[$\bullet$] \url{http://davidvgalbraith.com/how-i-fixed-atom/}  
+\end{itemize}}
+
+\subsubsection*{Tasks (file re.scala)}
 
-Transitions are edges between states labelled with a character. The
-idea is that if we are in state $Q_0$, say, and get an $a$, we can go
-to state $Q_1$. If we are in state $Q_2$ and get an $a$, we can stay
-in state $Q_2$; if we get a $b$ in $Q_2$, then can go to state
-$Q_0$. The main point of DFAs is that if we are in a state and get a
-character, it is always clear which is the next state---there can only
-be at most one. The task of Part 1 is to implement such DFAs in Scala
-using partial functions for the transitions.
+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:
 
-A string is accepted by a DFA, if we start in the starting state,
-follow all transitions according to the string; if we end up in an
-accepting state, then the string is accepted. If not, the string is
-not accepted. The technical idea is that DFAs can be used to
-accept strings from \emph{regular} languages. 
+\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}  
 
-\subsubsection*{Tasks}
 
 \begin{itemize}
-\item[(1)] Write a polymorphic function, called \texttt{share}, that
-  decides whether two sets share some elements (i.e.~the intersection
-  is not empty).\hfill[1 Mark]
- 
-\item[(2)] The transitions of DFAs will be implemented as partial
-  functions. These functions will have the type (state,
-  character)-pair to state, that is their input will be a (state,
-  character)-pair and they return a state. For example the transitions
-  of the DFA shown above can be defined as the following
-  partial function:
+\item[(1)] 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. The function
+  \textit{nullable}
+  is defined as follows:
+
+\begin{center}
+\begin{tabular}{lcl}
+$\textit{nullable}(\ZERO)$ & $\dn$ & $\textit{false}$\\
+$\textit{nullable}(\ONE)$  & $\dn$ & $\textit{true}$\\
+$\textit{nullable}(c)$     & $\dn$ & $\textit{false}$\\
+$\textit{nullable}(r_1 + r_2)$ & $\dn$ & $\textit{nullable}(r_1) \vee \textit{nullable}(r_2)$\\
+$\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]
+
+\item[(2)] Implement a function, called \textit{der}, by recursion over
+  regular expressions. It takes a character and a regular expression
+  as arguments and calculates the derivative regular expression according
+  to the rules:
+
+\begin{center}
+\begin{tabular}{lcl}
+$\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\
+$\textit{der}\;c\;(\ONE)$  & $\dn$ & $\ZERO$\\
+$\textit{der}\;c\;(d)$     & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\
+$\textit{der}\;c\;(r_1 + r_2)$ & $\dn$ & $(\textit{der}\;c\;r_1) + (\textit{der}\;c\;r_2)$\\
+$\textit{der}\;c\;(r_1 \cdot r_2)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r_1)$\\
+      & & $\textit{then}\;((\textit{der}\;c\;r_1)\cdot r_2) + (\textit{der}\;c\;r_2)$\\
+      & & $\textit{else}\;(\textit{der}\;c\;r_1)\cdot r_2$\\
+$\textit{der}\;c\;(r^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\
+\end{tabular}
+\end{center}
+
+For example given the regular expression $r = (a \cdot b) \cdot c$, the derivatives
+w.r.t.~the characters $a$, $b$ and $c$ are
 
-\begin{lstlisting}[language=Scala,numbers=none]
-val dfa_trans : PartialFunction[(State,Char), State] = 
-  { case (Q0, 'a') => Q1 
-    case (Q0, 'b') => Q0
-    case (Q1, 'a') => Q2 
-    case (Q1, 'b') => Q0
-    case (Q2, 'a') => Q2 
-    case (Q2, 'b') => Q0 
-  }
-\end{lstlisting}
+\begin{center}
+  \begin{tabular}{lcll}
+    $\textit{der}\;a\;r$ & $=$ & $(\ONE \cdot b)\cdot c$ & \quad($= r'$)\\
+    $\textit{der}\;b\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$\\
+    $\textit{der}\;c\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$
+  \end{tabular}
+\end{center}
+
+Let $r'$ stand for the first derivative, then taking the derivatives of $r'$
+w.r.t.~the characters $a$, $b$ and $c$ gives
+
+\begin{center}
+  \begin{tabular}{lcll}
+    $\textit{der}\;a\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$ \\
+    $\textit{der}\;b\;r'$ & $=$ & $((\ZERO \cdot b) + \ONE)\cdot c$ & \quad($= r''$)\\
+    $\textit{der}\;c\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$
+  \end{tabular}
+\end{center}
 
-  The main point of partial functions (as opposed to ``normal''
-  functions) is that they do not have to be defined everywhere. For
-  example the transitions above only mention characters $a$ and $b$,
-  but leave out any other characters. Partial functions come with a
-  method \texttt{isDefinedAt} that can be used to check whether an
-  input produces a result or not. For example
+One more example: Let $r''$ stand for the second derivative above,
+then taking the derivatives of $r''$ w.r.t.~the characters $a$, $b$
+and $c$ gives
+
+\begin{center}
+  \begin{tabular}{lcll}
+    $\textit{der}\;a\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$ \\
+    $\textit{der}\;b\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$\\
+    $\textit{der}\;c\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ONE$ &
+    (is $\textit{nullable}$)                      
+  \end{tabular}
+\end{center}
+
+Note, the last derivative can match the empty string, that is it is \textit{nullable}.\\
+\mbox{}\hfill\mbox{[1 Mark]}
+
+\item[(3)] Implement the function \textit{simp}, which recursively
+  traverses a regular expression from the inside to the outside, and
+  on the way simplifies every regular expression on the left (see
+  below) to the regular expression on the right, except it does not
+  simplify inside ${}^*$-regular expressions.
 
-\begin{lstlisting}[language=Scala,numbers=none]
-    dfa_trans.isDefinedAt((Q0, 'a'))
-    dfa_trans.isDefinedAt((Q0, 'c'))
-\end{lstlisting}   
+  \begin{center}
+\begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll}
+$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\ 
+$\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\ 
+$r \cdot \ONE$ & $\mapsto$ & $r$\\ 
+$\ONE \cdot r$ & $\mapsto$ & $r$\\ 
+$r + \ZERO$ & $\mapsto$ & $r$\\ 
+$\ZERO + r$ & $\mapsto$ & $r$\\ 
+$r + r$ & $\mapsto$ & $r$\\ 
+\end{tabular}
+  \end{center}
+
+  For example the regular expression
+  \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\]
+
+  simplifies to just $r_1$. \textbf{Hint:} Regular expressions can be
+  seen as trees and there are several methods for traversing
+  trees. One of them corresponds to the inside-out traversal, which is
+  sometimes also called post-order traversal'' you traverse inside the
+  tree and on the way up, you apply simplification rules.
+  Furthermore,
+  remember numerical expressions from school times: there you had expressions
+  like $u + \ldots + (1 \cdot x) - \ldots (z + (y \cdot 0)) \ldots$
+  and simplification rules that looked very similar to rules
+  above. You would simplify such numerical expressions by replacing
+  for example the $y \cdot 0$ by $0$, or $1\cdot x$ by $x$, and then
+  look whether more rules are applicable. If you organise the
+  simplification in an inside-out fashion, it is always clear which
+  rule should be applied next.\hfill[1 Mark]
+
+\item[(4)] Implement two functions: The first, called \textit{ders},
+  takes a list of characters and a regular expression as arguments, and
+  builds the derivative w.r.t.~the list as follows:
+
+\begin{center}
+\begin{tabular}{lcl}
+$\textit{ders}\;(Nil)\;r$ & $\dn$ & $r$\\
+  $\textit{ders}\;(c::cs)\;r$  & $\dn$ &
+    $\textit{ders}\;cs\;(\textit{simp}(\textit{der}\;c\;r))$\\
+\end{tabular}
+\end{center}
+
+Note that this function is different from \textit{der}, which only
+takes a single character.
 
-  \noindent
-  gives \texttt{true} in the first case and \texttt{false} in the
-  second.  There is also a method \texttt{lift} that transforms a
-  partial function into a ``normal'' function returning an optional
-  value: if the partial function is defined on the input, the lifted
-  function will return \texttt{Some}; if it is not defined, then
-  \texttt{None}.
-  
-  Write a function that takes a transition and a (state, character)-pair as arguments
-  and produces an optional state (the state specified by the partial transition
-  function whenever it is defined; if the transition function is undefined,
-  return \texttt{None}).\hfill\mbox{[1 Mark]}
+The second function, called \textit{matcher}, takes a string and a
+regular expression as arguments. It builds first the derivatives
+according to \textit{ders} and after that tests whether the resulting
+derivative regular expression can match the empty string (using
+\textit{nullable}).  For example the \textit{matcher} will produce
+true for the regular expression $(a\cdot b)\cdot c$ and the string
+$abc$, but false if you give it the string $ab$. \hfill[1 Mark]
+
+\item[(5)] Implement a function, called \textit{size}, by recursion
+  over regular expressions. If a regular expression is seen as a tree,
+  then \textit{size} should return the number of nodes in such a
+  tree. Therefore this function is defined as follows:
 
-\item[(3)] 
-  Write a function that ``lifts'' the function in (2) from characters to strings. That
-  is, write a function that takes a transition, a state and a list of characters
-  as arguments and produces the state generated by following the transitions for
-  each character in the list. For example if you are in state $Q_0$ in the DFA above
-  and have the list \texttt{List(a,a,a,b,b,a)}, then you need to return the
-  state $Q_1$ (as option since there might not be such a state in general).\\
-  \mbox{}\hfill\mbox{[1 Mark]}
-  
-\item[(4)] DFAs are defined as a triple: (starting state, transitions,
-  set of accepting states).  Write a function \texttt{accepts} that tests whether
-  a string is accepted by an DFA or not. For this start in the
-  starting state of the DFA, use the function under (3) to calculate
-  the state after following all transitions according to the
-  characters in the string. If the resulting state is an accepting state,
-  return \texttt{true}; otherwise \texttt{false}.\\\mbox{}\hfill\mbox{[1 Mark]}
+\begin{center}
+\begin{tabular}{lcl}
+$\textit{size}(\ZERO)$ & $\dn$ & $1$\\
+$\textit{size}(\ONE)$  & $\dn$ & $1$\\
+$\textit{size}(c)$     & $\dn$ & $1$\\
+$\textit{size}(r_1 + r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$\\
+$\textit{size}(r_1 \cdot r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$\\
+$\textit{size}(r^*)$ & $\dn$ & $1 + \textit{size}(r)$\\
+\end{tabular}
+\end{center}
+
+You can use \textit{size} in order to test how much the `evil' regular
+expression $(a^*)^* \cdot b$ grows when taking successive derivatives
+according the letter $a$ without simplification and then compare it to
+taking the derivative, but simplify the result.  The sizes
+are given in \texttt{re.scala}. \hfill[1 Mark]
+
+\item[(6)] You do not have to implement anything specific under this
+  task.  The purpose is that you will be marked for some ``power''
+  test cases. For example can your matcher decide withing 30 seconds
+  whether the regular expression $(a^*)^*\cdot b$ matches strings of the
+  form $aaa\ldots{}aaaa$, for say 1 Million $a$'s. And does simplification
+  simplify the regular expression
+
+  \[
+  \texttt{SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)}
+  \]  
+
+  \noindent correctly to just \texttt{ONE}, where \texttt{SEQ} is nested
+  50 or more times.\\
+  \mbox{}\hfill[1 Mark]
 \end{itemize}
 
+\subsection*{Background}
 
-\subsection*{Part 2 (Non-Deterministic Finite Automata)}
+Although easily implementable in Scala, the idea behind the derivative
+function might not so easy to be seen. To understand its purpose
+better, assume a regular expression $r$ can match strings of the form
+$c\!::\!cs$ (that means strings which start with a character $c$ and have
+some rest, or tail, $cs$). If you take the derivative of $r$ with
+respect to the character $c$, then you obtain a regular expression
+that can match all the strings $cs$.  In other words, the regular
+expression $\textit{der}\;c\;r$ can match the same strings $c\!::\!cs$
+that can be matched by $r$, except that the $c$ is chopped off.
+
+Assume now $r$ can match the string $abc$. If you take the derivative
+according to $a$ then you obtain a regular expression that can match
+$bc$ (it is $abc$ where the $a$ has been chopped off). If you now
+build the derivative $\textit{der}\;b\;(\textit{der}\;a\;r)$ you
+obtain a regular expression that can match the string $c$ (it is $bc$
+where $b$ is chopped off). If you finally build the derivative of this
+according $c$, that is
+$\textit{der}\;c\;(\textit{der}\;b\;(\textit{der}\;a\;r))$, you obtain
+a regular expression that can match the empty string. You can test
+whether this is indeed the case using the function nullable, which is
+what your matcher is doing.
 
-The main point of DFAs is that for every given state and character
-there is at most one next state (one if the transition is defined;
-none otherwise). However, this restriction to at most one state can be
-quite limiting for some applications.\footnote{Though there is a
-  curious fact that every (less restricted) NFA can be translated into
-  an ``equivalent'' DFA, whereby accepting means accepting the same
-  set of strings. However this might increase drastically the number
-  of states in the DFA.}  Non-Deterministic Automata (NFAs) remove
-this restriction: there can be more than one starting state, and given
-a state and a character there can be more than one next
-state. Consider for example the NFA
+The purpose of the $\textit{simp}$ function is to keep the regular
+expressions small. Normally the derivative function makes the regular
+expression bigger (see the SEQ case and the example in (2)) 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
+algorithm is fast throughout.  By the way, this algorithm is by Janusz
+Brzozowski who came up with the idea of derivatives in 1964 in his PhD
+thesis.
+
+\begin{center}\small
+\url{https://en.wikipedia.org/wiki/Janusz_Brzozowski_(computer_scientist)}
+\end{center}
+
+
+If you want to see how badly the regular expression matchers do in
+Java\footnote{Version 8 and below; Version 9 and above does not seem to be as
+  catastrophic, but still much worse than the regular expression
+  matcher based on derivatives.}, JavaScript 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{catastrophic9.java}, \texttt{catastrophic.js} and
+\texttt{catastrophic.py} on KEATS). Compare this with the matcher you
+have implemented. How long can the string of $a$'s be in your matcher
+and still stay within the 30 seconds time limit?
 
 \begin{center}
-\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
-    every state/.style={minimum size=0pt,
-      draw=blue!50,very thick,fill=blue!20},]
-\node[state,initial]  (R_1)  {$R_1$};
-\node[state,initial] (R_2) [above=of R_1] {$R_2$};
-\node[state, accepting] (R_3) [right=of R_1] {$R_3$};
-\path[->] (R_1) edge node [below]  {$b$} (R_3);
-\path[->] (R_2) edge [bend left] node [above]  {$a$} (R_3);
-\path[->] (R_1) edge [bend left] node  [left] {$c$} (R_2);
-\path[->] (R_2) edge [bend left] node  [right] {$a$} (R_1);
+\begin{tabular}{@{}cc@{}}
+\multicolumn{2}{c}{Graph: $(a^*)^*\cdot b$ and strings 
+           $\underbrace{a\ldots a}_{n}$}\bigskip\\
+  
+\begin{tikzpicture}
+\begin{axis}[
+    xlabel={$n$},
+    x label style={at={(1.05,0.0)}},
+    ylabel={time in secs},
+    y label style={at={(0.06,0.5)}},
+    enlargelimits=false,
+    xtick={0,5,...,30},
+    xmax=33,
+    ymax=45,
+    ytick={0,5,...,40},
+    scaled ticks=false,
+    axis lines=left,
+    width=6cm,
+    height=5.5cm, 
+    legend entries={Python, Java 8, JavaScript},  
+    legend pos=north west]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
+\end{axis}
 \end{tikzpicture}
+  & 
+\begin{tikzpicture}
+\begin{axis}[
+    xlabel={$n$},
+    x label style={at={(1.05,0.0)}},
+    ylabel={time in secs},
+    y label style={at={(0.06,0.5)}},
+    %enlargelimits=false,
+    %xtick={0,5000,...,30000},
+    xmax=65000,
+    ymax=45,
+    ytick={0,5,...,40},
+    scaled ticks=false,
+    axis lines=left,
+    width=6cm,
+    height=5.5cm, 
+    legend entries={Java 9},  
+    legend pos=north west]
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data};
+\end{axis}
+\end{tikzpicture}
+\end{tabular}  
 \end{center}
+\newpage
+
+\subsection*{Part 2 (4 Marks)}
+
+Coming from Java or C++, you might think Scala is a quite esoteric
+programming language.  But remember, some serious companies have built
+their business on
+Scala.\footnote{\url{https://en.wikipedia.org/wiki/Scala_(programming_language)\#Companies}}
+And there are far, far more esoteric languages out there. One is
+called \emph{brainf***}. You are asked in this part to implement an
+interpreter for this language.
+
+Urban M\"uller developed brainf*** in 1993.  A close relative of this
+language was already introduced in 1964 by Corado B\"ohm, an Italian
+computer pioneer, who unfortunately died a few months ago. The main
+feature of brainf*** is its minimalistic set of instructions---just 8
+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
+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
 
 \noindent
-where in state $R_2$ if we get an $a$, we can go to state $R_1$
-\emph{or} $R_3$. If we want to find out whether an NFA accepts a
-string, then we need to explore both possibilities. We will do this
-``exploration'' in the tasks below in a breadth-first manner.
-
+As mentioned above, brainf*** has 8 single-character commands, namely
+\texttt{'>'}, \texttt{'<'}, \texttt{'+'}, \texttt{'-'}, \texttt{'.'},
+\texttt{','}, \texttt{'['} and \texttt{']'}. Every other character is
+considered a comment.  Brainf*** operates on memory cells containing
+integers. For this it uses a single memory pointer that points at each
+stage to one memory cell. This pointer can be moved forward by one
+memory cell by using the command \texttt{'>'}, and backward by using
+\texttt{'<'}. The commands \texttt{'+'} and \texttt{'-'} increase,
+respectively decrease, by 1 the content of the memory cell to which
+the memory pointer currently points to. The commands for input/output
+are \texttt{','} and \texttt{'.'}. Output works by reading the content
+of the memory cell to which the memory pointer points to and printing
+it out as an ASCII character. Input works the other way, taking some
+user input and storing it in the cell to which the memory pointer
+points to. The commands \texttt{'['} and \texttt{']'} are looping
+constructs. Everything in between \texttt{'['} and \texttt{']'} is
+repeated until a counter (memory cell) reaches zero.  A typical
+program in brainf*** looks as follows:
 
-The feature of having more than one next state in NFAs will be
-implemented by having a \emph{set} of partial transition functions
-(DFAs had only one). For example the NFA shown above will be
-represented by the set of partial functions
-
-\begin{lstlisting}[language=Scala,numbers=none]
-val nfa_trans : NTrans = Set(
-  { case (R1, 'c') => R2 },
-  { case (R1, 'b') => R3 },
-  { case (R2, 'a') => R1 },
-  { case (R2, 'a') => R3 }
-)
-\end{lstlisting}
+\begin{center}
+\begin{verbatim}
+ ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++
+ ..+++.>>.<-.<.+++.------.--------.>>+.>++.
+\end{verbatim}
+\end{center}  
 
 \noindent
-The point is that the 3rd element in this set makes sure that in state $R_2$ and
-given an $a$, we can go to state $R_1$; and the 4th element, in $R_2$,
-given an $a$, we can also go to state $R_3$.  When following
-transitions from a state, we have to look at all partial functions in
-the set and generate the set of \emph{all} possible next states.
+This one prints out Hello World\ldots{}obviously. 
 
-\subsubsection*{Tasks}
+\subsubsection*{Tasks (file bf.scala)}
 
 \begin{itemize}
-\item[(5)]
-  Write a function \texttt{nnext} which takes a transition set, a state
-  and a character as arguments, and calculates all possible next states
-  (returned as set).\\
-  \mbox{}\hfill\mbox{[1 Mark]}
+\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 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
+  \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[(6)] Write a function \texttt{nnexts} which takes a transition
-  set, a \emph{set} of states and a character as arguments, and
-  calculates \emph{all} possible next states that can be reached from
-  any state in the set.\mbox{}\hfill\mbox{[1 Mark]}
+\item[(2b)] Write two functions, \texttt{jumpRight} and
+  \texttt{jumpLeft} that are needed to implement the loop constructs
+  of brainf***. They take a program (a \texttt{String}) and a program
+  counter (an \texttt{Int}) as argument and move right (respectively
+  left) in the string in order to find the \textbf{matching}
+  opening/closing bracket. For example, given the following program
+  with the program counter indicated by an arrow:
+
+  \begin{center}
+  \texttt{--[\barbelow{.}.+>--],>,++}
+  \end{center}
+
+  then the matching closing bracket is in 9th position (counting from 0) and
+  \texttt{jumpRight} is supposed to return the position just after this
+  
+  \begin{center}
+  \texttt{--[..+>--]\barbelow{,}>,++}
+  \end{center}
+
+  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):
 
-\item[(7)] Like in (3), write a function \texttt{nnextss} that lifts
-  \texttt{nnexts} from (6) from single characters to lists of characters.
-  \mbox{}\hfill\mbox{[1 Mark]}
-  
-\item[(8)] NFAs are also defined as a triple: (set of staring states,
-  set of transitions, set of accepting states).  Write a function
-  \texttt{naccepts} that tests whether a string is accepted by an NFA
-  or not. For this start in all starting states of the NFA, use the
-  function under (7) to calculate the set of states following all
-  transitions according to the characters in the string. If the
-  resulting set of states shares at least a single state with the set
-  of accepting states, return \texttt{true}; otherwise \texttt{false}.
-  Use the function under (1) in order to test whether these two sets
-  of states share any states or not.\mbox{}\hfill\mbox{[1 Mark]}
+  \begin{center}
+    \texttt{--[..+>-\barbelow{-}],>,++}
+    \qquad$\stackrel{\texttt{jumpLeft}}{\longrightarrow}$\qquad
+    \texttt{--[\barbelow{.}.+>--],>,++}
+  \end{center}
+
+  Unfortunately we have to take into account that there might be
+  other opening and closing brackets on the `way' to find the
+  matching bracket. For example in the brainf*** program
+
+  \begin{center}
+  \texttt{--[\barbelow{.}.[+>]--],>,++}
+  \end{center}
+
+  we do not want to return the index for the \texttt{'-'} in the 9th
+  position, but the program counter for \texttt{','} in 12th
+  position. The easiest to find out whether a bracket is matched is by
+  using levels (which are the third argument in \texttt{jumpLeft} and
+  \texttt{jumpLeft}). In case of \texttt{jumpRight} you increase the
+  level by one whenever you find an opening bracket and decrease by
+  one for a closing bracket. Then in \texttt{jumpRight} you are looking
+  for the closing bracket on level \texttt{0}. For \texttt{jumpLeft} you
+  do the opposite. In this way you can find \textbf{matching} brackets
+  in strings such as
+
+  \begin{center}
+  \texttt{--[\barbelow{.}.[[-]+>[.]]--],>,++}
+  \end{center}
+
+  for which \texttt{jumpRight} should produce the position:
+
+  \begin{center}
+  \texttt{--[..[[-]+>[.]]--]\barbelow{,}>,++}
+  \end{center}
+
+  It is also possible that the position returned by \texttt{jumpRight} or
+  \texttt{jumpLeft} is outside the string in cases where there are
+  no matching brackets. For example
+
+  \begin{center}
+  \texttt{--[\barbelow{.}.[[-]+>[.]]--,>,++}
+  \qquad$\stackrel{\texttt{jumpRight}}{\longrightarrow}$\qquad
+  \texttt{--[..[[-]+>[.]]-->,++\barbelow{\;\phantom{+}}}
+  \end{center}
+  \hfill[1 Mark]
 
-\item[(9)] Since we explore in functions (6) and (7) all possible next
-  states, we decide whether a string is accepted in a breadth-first
-  manner. (Depth-first would be to choose one state, follow all next
-  states of this single state; check whether it leads to an accepting
-  state. If not, we backtrack and choose another state). The
-  disadvantage of breadth-first search is that at every step a
-  non-empty set of states are ``active''\ldots{} states that need to
-  be followed at the same time.  Write similar functions as in (7) and
-  (8), but instead of returning states or a boolean, calculate the
-  number of states that need to be followed in each step. The function
-  \texttt{max\_accept} should then return the maximum of all these
-  numbers.
+
+\item[(2c)] Write a recursive function \texttt{run} that executes a
+  brainf*** program. It takes a program, a program counter, a memory
+  pointer and a memory as arguments. If the program counter is outside
+  the program string, the execution stops and \texttt{run} returns the
+  memory. If the program counter is inside the string, it reads the
+  corresponding character and updates the program counter \texttt{pc},
+  memory pointer \texttt{mp} and memory \texttt{mem} according to the
+  rules shown in Figure~\ref{comms}. It then calls recursively
+  \texttt{run} with the updated data.
+
+  Write another function \texttt{start} that calls \texttt{run} with a
+  given brainfu** program and memory, and the program counter and memory pointer
+  set to~$0$. Like \texttt{run} it returns the memory after the execution
+  of the program finishes. You can test your brainf**k interpreter with the
+  Sierpinski triangle or the Hello world programs or have a look at
 
-  As a test case, consider again the NFA shown above. At the beginning
-  the number of active states will be 2 (since there are two starting
-  states, namely $R_1$ and $R_2$). If we get an $a$, there will be
-  still 2 active states, namely $R_1$ and $R_3$ both reachable from
-  $R_2$. There is no transition for $a$ and $R_1$. So for a string,
-  say, $ab$ which is accepted by the NFA, the maximum number of active
-  states is 2 (it is not possible that all three states of this NFA
-  are active at the same time; is it possible that no state is
-  active?).  \hfill\mbox{[2 Marks]}
+  \begin{center}
+  \url{https://esolangs.org/wiki/Brainfuck}
+  \end{center}\hfill[2 Marks]
+  
+  \begin{figure}[p]
+  \begin{center}
+    \begin{tabular}{|@{}p{0.8cm}|l|}
+      \hline
+      \hfill\texttt{'>'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
+                       $\bullet$ & $\texttt{pc} + 1$\\
+                       $\bullet$ & $\texttt{mp} + 1$\\
+                       $\bullet$ & \texttt{mem} unchanged
+                     \end{tabular}\\\hline   
+      \hfill\texttt{'<'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
+                       $\bullet$ & $\texttt{pc} + 1$\\
+                       $\bullet$ & $\texttt{mp} - 1$\\
+                       $\bullet$ & \texttt{mem} unchanged
+                     \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 -> mem(mp) + 1}\\
+                     \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 -> mem(mp) - 1}\\
+                     \end{tabular}\\\hline   
+      \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\\
+                     \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}{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}\\
+                       $\bullet$ & $\texttt{pc = jumpRight(prog, pc + 1, 0)}$\\
+                       $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\
+                       \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) != 0} then}\\
+                       $\bullet$ & $\texttt{pc} + 1$\\
+                       $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
+                     \end{tabular}
+                     \\\hline   
+      \hfill\texttt{']'} & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
+                       \multicolumn{2}{@{}l}{if \texttt{mem(mp) != 0} then}\\
+                       $\bullet$ & $\texttt{pc = jumpLeft(prog, pc - 1, 0)}$\\
+                       $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\medskip\\
+                       \multicolumn{2}{@{}l}{otherwise if \texttt{mem(mp) == 0} then}\\
+                       $\bullet$ & $\texttt{pc} + 1$\\
+                       $\bullet$ & $\texttt{mp}$ and \texttt{mem} unchanged\\
+                     \end{tabular}\\\hline   
+      any other char & \begin{tabular}[t]{@{}l@{\hspace{2mm}}l@{}}
+                         $\bullet$ & $\texttt{pc} + 1$\\
+                         $\bullet$ & \texttt{mp} and \texttt{mem} unchanged
+                       \end{tabular}\\
+      \hline                 
+    \end{tabular}
+  \end{center}
+  \caption{The rules for how commands in the brainf*** language update the program counter \texttt{pc},
+    memory pointer \texttt{mp} and memory \texttt{mem}.\label{comms}}
+  \end{figure}
+\end{itemize}\bigskip  
 
-  
-\end{itemize}
-  
+
+
 
 \end{document}
 




