--- a/coursework/cw01.tex Fri Sep 26 14:40:49 2014 +0100
+++ b/coursework/cw01.tex Sat Sep 27 00:37:02 2014 +0100
@@ -4,7 +4,7 @@
\begin{document}
-\section*{Coursework 1}
+\section*{Coursework 1 (Strand 1)}
This coursework is worth 5\% and is due on 13 October at 16:00. You
are asked to implement a regular expression matcher and submit a
@@ -17,9 +17,9 @@
\subsubsection*{Disclaimer}
-It should be understood that the work submitted represents your own effort.
-You have not copied from anyone else. An exception is the Scala code I
-showed during the lectures, which you can use.\bigskip
+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, which you can use.\bigskip
\subsubsection*{Tasks}
@@ -62,16 +62,10 @@
\noindent
whereby in the last clause the set $\mathbb{A}$ stands for the set of
\emph{all} strings. So $\sim{}r$ means `all the strings that $r$
-cannot match'. We assume ranges like $[a\mbox{-}z0\mbox{-}9]$ are a
-shorthand for the regular expression
+cannot match'.
-\[
-[a b c d\ldots z 0 1\ldots 9]\;.
-\]
-
-\noindent
Be careful that your implementation of $nullable$ and $der$ satisfies
-for every $r$ the following two properties:
+for every $r$ the following two properties (see also Question 2):
\begin{itemize}
\item $nullable(r)$ if and only if $[]\in L(r)$
@@ -79,11 +73,13 @@
\end{itemize}
\noindent
-{\bf Important!} Your implementation should have explicit cases for the
-basic regular expressions, but also for the extended regular expressions.
-That means do not treat the extended regular expressions by just translating
-them into the basic ones. See also Question 2, where you asked to give
-the rules for \textit{nullable} and \textit{der}.
+{\bf Important!} Your implementation should have explicit cases for
+the basic regular expressions, but also explicit cases for the
+extended regular expressions. That means do not treat the extended
+regular expressions by just translating them into the basic ones. 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)}
@@ -94,7 +90,8 @@
This question does not require any implementation. From the lectures
you have seen the definitions for the functions \textit{nullable} and
-\textit{der}. Give the rules for the extended regular expressions:
+\textit{der} for the basic regular expressions. Give the rules for
+the extended regular expressions:
\begin{center}
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
@@ -103,11 +100,11 @@
$nullable(r^?)$ & $\dn$ & $?$\\
$nullable(r^{\{n,m\}})$ & $\dn$ & $?$\\
$nullable(\sim{}r)$ & $\dn$ & $?$\medskip\\
-$der c ([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\
-$der c (r^+)$ & $\dn$ & $?$\\
-$der c (r^?)$ & $\dn$ & $?$\\
-$der c (r^{\{n,m\}})$ & $\dn$ & $?$\\
-$der c (\sim{}r)$ & $\dn$ & $?$\\
+$der\, c\, ([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\
+$der\, c\, (r^+)$ & $\dn$ & $?$\\
+$der\, c\, (r^?)$ & $\dn$ & $?$\\
+$der\, c\, (r^{\{n,m\}})$ & $\dn$ & $?$\\
+$der\, c\, (\sim{}r)$ & $\dn$ & $?$\\
\end{tabular}
\end{center}
@@ -142,7 +139,8 @@
\subsection*{Question 4 (marked with 1\%)}
-Consider the regular expression $/ \cdot * \cdot
+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
this regular expression. Answer yes or no.