coursework/cw01.tex
changeset 260 65d1ea0e989f
parent 259 e5f4b8ff23b8
child 272 1446bc47a294
--- 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.