afl-material: comparison coursework/cw01.tex

equal deleted inserted replaced

-:e74c696821a2
+:010c5a03dca2
 \begin{document}
 \section*{Coursework 1 (Strand 1)}
-This coursework is worth 5\% and is due on 20 October at
+This coursework is worth 4\% and is due on 20 October at
 16: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.
 \subsubsection*{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 use.\bigskip
+uploaded to KEATS, which you can freely use.\bigskip
-\subsubsection*{Tasks}
+\subsubsection*{Task}
 The task is to implement a regular expression matcher based on
-derivatives. The implementation should be able to deal with the usual
+derivatives of regular expressions. The implementation should
-(basic) regular expressions
+be able to deal with the usual (basic) regular expressions
 \[
-\varnothing, \epsilon, c, r_1 + r_2, r_1 \cdot r_2, r^*
+\ZERO,\; \ONE,\; c,\; r_1 + r_2,\; r_1 \cdot r_2,\; r^*
 \]
 \noindent
 but also with the following extended regular expressions:
 $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 In the case of $r^{\{n,m\}}$ we have the convention
+\noindent In the case of $r^{\{n,m\}}$ you can assume the
-that $0 \le n \le m$. The meanings of the extended regular
+convention that $0 \le n \le m$. The meanings of the extended
-expressions are
+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$\\
 \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$
+represented by, say, the type \pcode{Char}). So $\sim{}r$
 means `all the strings that $r$ cannot match'.
 Be careful that your implementation of \textit{nullable} and
 \textit{der} satisfies for every $r$ the following two
 properties (see also Question 2):
 where you are asked to explicitly give the rules for
 \textit{nullable} and \textit{der} for the extended regular
 expressions.
-\subsection*{Question 1 (unmarked)}
+\subsection*{Question 1}
 What is your King's email address (you will need it in
 Question 3)?
-\subsection*{Question 2 (marked with 2\%)}
+\subsection*{Question 2}
 This question does not require any implementation. From the
 lectures you have seen the definitions for the functions
 \textit{nullable} and \textit{der} for the basic regular
 expressions. Give the rules for the extended regular
 \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 3 (marked with 1\%)}
+\subsection*{Question 3}
 Implement 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 email
 address. When calculating the derivative, simplify all regular
-expressions as much as possible, but at least apply the
+expressions as much as possible by applying the
-following six simplification rules:
+following 7 simplification rules:
 \begin{center}
 \begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll}
 $r \cdot \varnothing$ & $\mapsto$ & $\varnothing$\\
 $\varnothing \cdot r$ & $\mapsto$ & $\varnothing$\\
 $\varnothing + r$ & $\mapsto$ & $r$\\
 $r + r$ & $\mapsto$ & $r$\\
 \end{tabular}
 \end{center}
-\noindent
+\noindent Write down your simplified derivative in a readable
-Write down your simplified derivative in the ``mathematicical''
+notation using parentheses where necessary. That means you
-notation using parentheses where necessary. That means you should
+should use the infix notation $+$, $\cdot$, $^*$ and so on,
-use the more readable infix notation $+$, $\cdot$ and $^*$,
 instead of code.
-\subsection*{Question 4 (marked with 1\%)}
+\subsection*{Question 4}
 Suppose \textit{[a-z]} stands for the range regular expression
 $[a,b,c,\ldots,z]$.  Consider the regular expression $/ \cdot * \cdot
 (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot *
 \cdot /$ and decide wether the following four strings are matched by
 \item \texttt{"/*foobar*/"}
 \item \texttt{"/*test*/test*/"}
 \item \texttt{"/*test/*test*/"}
 \end{enumerate}
-\subsection*{Question 5 (marked with 1\%)}
+\noindent
+Also test your regular expression matcher with the regular
+expression $a^{\{3,5\}}$ and the strings
+\begin{enumerate}
+\setcounter{enumi}{4}
+\item \texttt{aa}
+\item \texttt{aaa}
+\item \texttt{aaaaa}
+\item \texttt{aaaaaa}
+\end{enumerate}
+\noindent
+Does your matcher produce the expected results?
+\subsection*{Question 5}
 Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be
 $(a^{\{19,19\}}) \cdot (a^?)$.  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

changeset 418	010c5a03dca2
parent 395	e57d3d92b856
child 439	7611ace6a93b