% !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: