# HG changeset patch # User Christian Urban # Date 1727689669 -3600 # Node ID 4189cb63e5db58fd4a1c69484c3980900907e212 # Parent 94f5cce73a4f941059bb3c4a47c1079e575d4261 updated diff -r 94f5cce73a4f -r 4189cb63e5db cws/cw01.pdf Binary file cws/cw01.pdf has changed diff -r 94f5cce73a4f -r 4189cb63e5db cws/cw01.tex --- a/cws/cw01.tex Sun Sep 29 18:46:02 2024 +0100 +++ b/cws/cw01.tex Mon Sep 30 10:47:49 2024 +0100 @@ -11,17 +11,16 @@ \begin{document} \newcolumntype{C}[1]{>{\centering}m{#1}} -\section*{Coursework 1} +\section*{Coursework 1 (Update for 2024: CW is OPTIONAL but recommended)} -This coursework is worth 5\% and is due on \cwONE{} 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 need to submit your written -answers as pdf---see attached questionaire. Code send as code. If you use -Scala in your code, a good place to start is the file \texttt{re3.sc} -that is uploaded to Github. +%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 need to submit your +%written answers as pdf---see attached questionaire. Code send as +%code. If you use Scala in your code, a good place to start is the file +%\texttt{re3.sc} that is uploaded to Github. %Please package everything %inside a zip-file that creates a directory with the name @@ -31,19 +30,19 @@ -\subsubsection*{Disclaimer\alert} +%\subsubsection*{Disclaimer\alert} -It should be understood that the work you submit represents -your \textbf{own} effort. You have not copied from anyone else -including CoPilot, ChatGPT \& Co. An -exception is the Scala code I showed during the lectures or -uploaded to KEATS, which you can freely use. Do not -be tempted to ask Github Copilot for help or do any other -shenanigans like this!\bigskip +%It should be understood that the work you submit represents +%your \textbf{own} effort. You have not copied from anyone else +%including CoPilot, ChatGPT \& Co. An +%exception is the Scala code I showed during the lectures or +%uploaded to KEATS, which you can freely use. Do not +%be tempted to ask Github Copilot for help or do any other +%shenanigans like this!\bigskip -\noindent -If you have any questions, please send me an email in \textbf{good} -time!\bigskip +%\noindent +%If you have any questions, please send me an email in \textbf{good} +%time!\bigskip \subsection*{Task} @@ -82,13 +81,13 @@ \code{RANGE}, \code{PLUS}, \code{OPTIONAL}, \code{INTER}, \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, +by just translating them into the basic ones. See also Question 1, 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} +\noindent is \emph{not} allowed as answer in Question 1 and \emph{not} allowed in your code.\medskip \noindent @@ -117,7 +116,7 @@ \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): +two properties (see also Question 1): \begin{itemize} \item $\textit{nullable}(r)$ if and only if $[]\in L(r)$ @@ -126,21 +125,21 @@ -\subsection*{Question 1 (Unmarked)} - -What is your King's email address (you will need it in -Question 5)? Also, could you please let me know whether you are -a BSc / MSci and the year you are in (in case of MSci). Thanks! +%\subsection*{Question 1 (Unmarked)} +% +%What is your King's email address (you will need it in +%Question 5)? Also, could you please let me know whether you are +%a BSc / MSci and the year you are in (in case of MSci). Thanks! -\subsection*{Question 2 (Unmarked)} +%\subsection*{Question 2 (Unmarked)} +% +%Can you please also 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. -Can you please also 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} +\subsection*{Question 1} From the lectures you have seen the definitions for the functions \textit{nullable} and \textit{der} for the basic regular @@ -180,7 +179,7 @@ Does your matcher produce the expected results? Make sure you also test corner-cases, like $a^{\{0\}}$! -\subsection*{Question 4} +\subsection*{Question 2} As you can see, there are a number of explicit regular expressions that deal with single or several characters, for example: @@ -235,7 +234,7 @@ In an ideal world one would do this task first, but this might confuse you with what you need to do in the previous question. -\subsection*{Question 5} +\subsection*{Question 3} Suppose $[a\mbox{-}z0\mbox{-}9\_\,.\mbox{-}]$ stands for the regular expression @@ -271,7 +270,7 @@ instead of raw code.\bigskip -\subsection*{Question 6} +\subsection*{Question 4} Implement the simplification rules in your regular expression matcher. Consider the regular expression $/ \cdot * \cdot @@ -286,7 +285,7 @@ \item \texttt{"/*test/*test*/"} \end{enumerate} -\subsection*{Question 7} +\subsection*{Question 5} Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be $(a^{\{19,19\}}) \cdot (a^?)$.\medskip @@ -339,7 +338,7 @@ \uline{\hfill}\bigskip\bigskip \noindent -\textbf{Question 3:} +\textbf{Question 1:} \begin{center} \def\arraystretch{1.6} @@ -379,7 +378,7 @@ \noindent -\textbf{Question 4:} +\textbf{Question 2:} \begin{center} \def\arraystretch{1.6} @@ -399,7 +398,7 @@ \newpage \noindent -\textbf{Question 5 (`mathematical' notation):} +\textbf{Question 3 (`mathematical' notation):} \noindent \uline{\hfill}\medskip @@ -417,7 +416,7 @@ \uline{\hfill}\bigskip\bigskip \noindent -\textbf{Question 6:}\medskip +\textbf{Question 4:}\medskip \noindent \textbf{1)}\; Yes / No\qquad @@ -427,7 +426,7 @@ \noindent -\textbf{Question 7:}\medskip +\textbf{Question 5:}\medskip \def\arraystretch{1.5} \begin{tabular}{l|c|c}