--- a/coursework/cw01.tex Tue Sep 01 15:57:55 2020 +0100
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,337 +0,0 @@
-% !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: