diff -r e5f4b8ff23b8 -r 65d1ea0e989f coursework/cw01.tex --- 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.