diff -r 02bc5af1c5f2 -r 1f1a293549c1 cws/cw01.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/cws/cw01.tex	Tue Sep 01 16:00:37 2020 +0100
@@ -0,0 +1,337 @@
+% !TEX program = xelatex
+\documentclass{article}
+\usepackage{../style}
+\usepackage{../langs}
+
+\usepackage{array}
+
+
+\begin{document}
+\newcolumntype{C}[1]{>{\centering}m{#1}}
+
+\section*{Coursework 1}
+
+This coursework is worth 5\% and is due on \cwONE{} at 18:00. You are
+asked to implement a regular expression matcher and submit a document
+containing the answers for the questions below. You can do the
+implementation in any programming language you like, but you need to
+submit the source code with which you answered the questions,
+otherwise a mark of 0\% will be awarded. You can submit your answers
+in a txt-file or pdf.  Code send as code. Please package everything
+inside a zip-file that creates a directory with the name
+\[\texttt{YournameYourfamilyname}\]
+
+\noindent on my end. Thanks!
+
+
+
+\subsubsection*{Disclaimer\alert}
+
+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
+
+\noindent
+If you have any questions, please send me an email in \textbf{good}
+time.\bigskip
+
+\subsection*{Task}
+
+The task is to implement a regular expression matcher based on
+derivatives of regular expressions. The implementation should
+be able to deal with the usual (basic) regular expressions
+
+\[
+\ZERO,\; \ONE,\; c,\; r_1 + r_2,\; r_1 \cdot r_2,\; r^*
+\]
+
+\noindent
+but also with the following extended regular expressions:
+
+\begin{center}
+\begin{tabular}{ll}
+  $[c_1,c_2,\ldots,c_n]$ & a set of characters---for character ranges\\
+  $r^+$ & one or more times $r$\\
+  $r^?$ & optional $r$\\
+  $r^{\{n\}}$ & exactly $n$-times\\
+  $r^{\{..m\}}$ & zero or more times $r$ but no more than $m$-times\\
+  $r^{\{n..\}}$ & at least $n$-times $r$\\
+  $r^{\{n..m\}}$ & at least $n$-times $r$ but no more than $m$-times\\
+  $\sim{}r$ & not-regular-expression of $r$\\
+\end{tabular}
+\end{center}
+
+\noindent You can assume that $n$ and $m$ are greater or equal than
+$0$. In the case of $r^{\{n,m\}}$ you can also assume $0 \le n \le m$.\bigskip
+
+\noindent {\bf Important!} Your implementation should have explicit
+case classes  for the basic regular expressions, but also explicit case
+classes for
+the extended regular expressions.\footnote{Please call them
+  \code{RANGE}, \code{PLUS}, \code{OPTIONAL}, \code{NTIMES},
+  \code{UPTO}, \code{FROM} and \code{BETWEEN}.} 
+  That means do not treat the extended regular expressions
+by just translating them into the basic ones. See also Question 3,
+where you are asked to explicitly give the rules for \textit{nullable}
+and \textit{der} for the extended regular expressions. Something like
+
+\[der\,c\,(r^+) \dn der\,c\,(r\cdot r^*)\]
+
+\noindent is \emph{not} allowed as answer in Question 3 and \emph{not}
+allowed in your code.\medskip
+
+\noindent
+The meanings of the extended regular expressions are
+
+\begin{center}
+\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}
+  $L([c_1,c_2,\ldots,c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\ 
+  $L(r^+)$                  & $\dn$ & $\bigcup_{1\le i}.\;L(r)^i$\\
+  $L(r^?)$                  & $\dn$ & $L(r) \cup \{[]\}$\\
+  $L(r^{\{n\}})$             & $\dn$ & $L(r)^n$\\
+  $L(r^{\{..m\}})$           & $\dn$ & $\bigcup_{0\le i \le m}.\;L(r)^i$\\
+  $L(r^{\{n..\}})$           & $\dn$ & $\bigcup_{n\le i}.\;L(r)^i$\\
+  $L(r^{\{n..m\}})$          & $\dn$ & $\bigcup_{n\le i \le m}.\;L(r)^i$\\
+  $L(\sim{}r)$              & $\dn$ & $\Sigma^* - L(r)$
+\end{tabular}
+\end{center}
+
+\noindent whereby in the last clause the set $\Sigma^*$ stands
+for the set of \emph{all} strings over the alphabet $\Sigma$
+(in the implementation the alphabet can be just what is
+represented by, say, the type \pcode{Char}). So $\sim{}r$
+means in effect ``all the strings that $r$ cannot match''.\medskip 
+
+\noindent
+Be careful that your implementation of \textit{nullable} and
+\textit{der} satisfies for every regular expression $r$ the following
+two properties (see also Question 3):
+
+\begin{itemize}
+\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
+\item $L(der\,c\,r) = Der\,c\,(L(r))$
+\end{itemize}
+
+
+
+\subsection*{Question 1 (Unmarked)}
+
+What is your King's email address (you will need it in
+Question 5)?
+
+\subsection*{Question 2 (Unmarked)}
+
+Can you please list all programming languages in which you have
+already written programs (include only instances where you have spent
+at least a good working day fiddling with a program)?  This is just
+for my curiosity to estimate what your background is.
+
+\subsection*{Question 3}
+
+From the
+lectures you have seen the definitions for the functions
+\textit{nullable} and \textit{der} for the basic regular
+expressions. Implement and write down the rules for the extended
+regular expressions:
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+  $\textit{nullable}([c_1,c_2,\ldots,c_n])$  & $\dn$ & $?$\\
+  $\textit{nullable}(r^+)$                   & $\dn$ & $?$\\
+  $\textit{nullable}(r^?)$                   & $\dn$ & $?$\\
+  $\textit{nullable}(r^{\{n\}})$              & $\dn$ & $?$\\
+  $\textit{nullable}(r^{\{..m\}})$            & $\dn$ & $?$\\
+  $\textit{nullable}(r^{\{n..\}})$            & $\dn$ & $?$\\
+  $\textit{nullable}(r^{\{n..m\}})$           & $\dn$ & $?$\\
+  $\textit{nullable}(\sim{}r)$              & $\dn$ & $?$
+\end{tabular}
+\end{center}
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+  $der\, c\, ([c_1,c_2,\ldots,c_n])$  & $\dn$ & $?$\\
+  $der\, c\, (r^+)$                   & $\dn$ & $?$\\
+  $der\, c\, (r^?)$                   & $\dn$ & $?$\\
+  $der\, c\, (r^{\{n\}})$              & $\dn$ & $?$\\
+  $der\, c\, (r^{\{..m\}})$           & $\dn$ & $?$\\
+  $der\, c\, (r^{\{n..\}})$           & $\dn$ & $?$\\
+  $der\, c\, (r^{\{n..m\}})$           & $\dn$ & $?$\\
+  $der\, c\, (\sim{}r)$               & $\dn$ & $?$\\
+\end{tabular}
+\end{center}
+
+\noindent
+Remember your definitions have to satisfy the two properties
+
+\begin{itemize}
+\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$
+\item $L(der\,c\,r)) = Der\,c\,(L(r))$
+\end{itemize}
+
+\noindent
+Given the definitions of \textit{nullable} and \textit{der}, it is
+easy to implement a regular expression matcher.  Test your regular
+expression matcher with (at least) the examples:
+
+
+\begin{center}
+\def\arraystretch{1.2}  
+\begin{tabular}{@{}r|m{3mm}|m{6mm}|m{6mm}|m{10mm}|m{6mm}|m{10mm}|m{10mm}|m{10mm}}
+  string & $a^?$ & $\sim{}a$ & $a^{\{3\}}$ & $(a^?)^{\{3\}}$ & $a^{\{..3\}}$ &
+     $(a^?)^{\{..3\}}$ & $a^{\{3..5\}}$ & $(a^?)^{\{3..5\}}$ \\\hline
+  $[]$           &&&&&&& \\\hline 
+  \texttt{a}     &&&&&&& \\\hline 
+  \texttt{aa}    &&&&&&& \\\hline 
+  \texttt{aaa}   &&&&&&& \\\hline 
+  \texttt{aaaaa} &&&&&&& \\\hline 
+  \texttt{aaaaaa}&&&&&&& \\
+\end{tabular}
+\end{center}
+
+\noindent
+Does your matcher produce the expected results? Make sure you
+also test corner-cases, like $a^{\{0\}}$!
+
+\subsection*{Question 4}
+
+As you can see, there are a number of explicit regular expressions
+that deal with single or several characters, for example:
+
+\begin{center}
+\begin{tabular}{ll}
+  $c$ & matches a single character\\  
+  $[c_1,c_2,\ldots,c_n]$ & matches a set of characters---for character ranges\\
+  $\textit{ALL}$ & matches any character
+\end{tabular}
+\end{center}
+
+\noindent
+The latter is useful for matching any string (for example
+by using $\textit{ALL}^*$). In order to avoid having an explicit constructor
+for each case, we can generalise all these cases and introduce a single
+constructor $\textit{CFUN}(f)$ where $f$ is a function from characters
+to booleans. In Scala code this would look as follows:
+
+\begin{lstlisting}[numbers=none]
+abstract class Rexp
+...
+case class CFUN(f: Char => Boolean) extends Rexp 
+\end{lstlisting}\smallskip
+
+\noindent
+The idea is that the function $f$ determines which character(s)
+are matched, namely those where $f$ returns \texttt{true}.
+In this question implement \textit{CFUN} and define
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+  $\textit{nullable}(\textit{CFUN}(f))$  & $\dn$ & $?$\\
+  $\textit{der}\,c\,(\textit{CFUN}(f))$  & $\dn$ & $?$
+\end{tabular}
+\end{center}
+
+\noindent in your matcher and then also give definitions for
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+  $c$  & $\dn$ & $\textit{CFUN}(?)$\\
+  $[c_1,c_2,\ldots,c_n]$  & $\dn$ & $\textit{CFUN}(?)$\\
+  $\textit{ALL}$  & $\dn$ & $\textit{CFUN}(?)$
+\end{tabular}
+\end{center}
+
+\noindent
+You can either add the constructor $CFUN$ to your implementation in
+Question 3, or you can implement this questions first
+and then use $CFUN$ instead of \code{RANGE} and \code{CHAR} in Question 3.
+
+
+\subsection*{Question 5}
+
+Suppose $[a\mbox{-}z0\mbox{-}9\_\,.\mbox{-}]$ stands for the regular expression
+
+\[[a,b,c,\ldots,z,0,\dots,9,\_,.,\mbox{-}]\;.\]
+
+\noindent
+Define in your code the following regular expression for email addresses
+
+\[
+([a\mbox{-}z0\mbox{-}9\_\,.-]^+)\cdot @\cdot ([a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot ([a\mbox{-}z\,.]^{\{2,6\}})
+\]
+
+\noindent and calculate the derivative according to your own email
+address. When calculating the derivative, simplify all regular
+expressions as much as possible by applying the
+following 7 simplification rules:
+
+\begin{center}
+\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}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}
+
+\noindent Write down your simplified derivative in a readable
+notation using parentheses where necessary. That means you
+should use the infix notation $+$, $\cdot$, $^*$ and so on,
+instead of raw code.\bigskip
+
+
+\subsection*{Question 6}
+
+Implement the simplification rules in your regular expression matcher.
+Consider the regular expression $/ \cdot * \cdot
+(\sim{}(\textit{ALL}^* \cdot * \cdot / \cdot \textit{ALL}^*)) \cdot *
+\cdot /$ and decide whether the following four strings are matched by
+this regular expression. Answer yes or no.
+
+\begin{enumerate}
+\item \texttt{"/**/"}
+\item \texttt{"/*foobar*/"}
+\item \texttt{"/*test*/test*/"}
+\item \texttt{"/*test/*test*/"}
+\end{enumerate}
+
+\subsection*{Question 7}
+
+Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be
+$(a^{\{19,19\}}) \cdot (a^?)$.\medskip
+
+\noindent
+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
+with yes or no. \medskip
+
+\noindent
+These are strings are meant to be entirely made up of $a$s. Be careful
+when copy-and-pasting the strings so as to not forgetting any $a$ and
+to not introducing any other character.
+
+\begin{enumerate}
+\setcounter{enumi}{4}
+\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ 
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
+\end{enumerate}
+
+
+
+\end{document}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: t
+%%% End: