% !TEX program = xelatex\documentclass{article}\usepackage{../style}\usepackage{../langs}\usepackage[normalem]{ulem}\usepackage{array}%TEST\begin{document}\newcolumntype{C}[1]{>{\centering}m{#1}}\section*{Coursework 1}This coursework is worth 5\% and is due on \cwONE{} at 16:00. You areasked to implement a regular expression matcher and submit a documentcontaining the answers for the questions below. You can do theimplementation in any programming language you like, but you need tosubmit the source code with which you answered the questions,otherwise a mark of 0\% will be awarded. You need to submit your writtenanswers as pdf---see attached questionaire. Code send as code. If you useScala 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%\[\texttt{YournameYourfamilyname}\]%%\noindent on my end. Thanks!\subsubsection*{Disclaimer\alert}It should be understood that the work you submit representsyour \textbf{own} effort. You have not copied from anyone elseincluding CoPilot, ChatGPT \& Co. Anexception is the Scala code I showed during the lectures oruploaded to KEATS, which you can freely use. Do notbe tempted to ask Github Copilot for help or do any othershenanigans like this!\bigskip\noindentIf you have any questions, please send me an email in \textbf{good}time!\bigskip\subsection*{Task}The task is to implement a regular expression matcher based onderivatives of regular expressions. The implementation shouldbe able to deal with the usual (basic) regular expressions\[\ZERO,\; \ONE,\; c,\; r_1 + r_2,\; r_1 \cdot r_2,\; r^*\]\noindentbut also with the following extended regular expressions:\begin{center}\begin{tabular}{ll} $[c_1,c_2,\ldots,c_n]$ & a set of characters---for character ranges\\ $r^+$ & one or more times $r$\\ $r^?$ & optional $r$\\ $r_1 \,\&\, r_2$ & intersection (matched by both $r_1$ and $r_2$)\\ $r^{\{n\}}$ & exactly $n$-times\\ $r^{\{..m\}}$ & zero or more times $r$ but no more than $m$-times\\ $r^{\{n..\}}$ & at least $n$-times $r$\\ $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 You can assume that $n$ and $m$ are greater or equal than$0$. In the case of $r^{\{n,m\}}$ you can also assume $0 \le n \le m$.\bigskip\noindent {\bf Important!} Your implementation should have explicitcase classes for the basic regular expressions, but also explicit caseclasses forthe extended regular expressions.\footnote{Please call them \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 expressionsby just translating them into the basic ones. See also Question 3,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}allowed in your code.\medskip\noindentThe meanings of the extended 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$\\ $L(r^?)$ & $\dn$ & $L(r) \cup \{[]\}$\\ $L(r_1 \,\&\, r_2)$ & $\dn$ & $L(r_1) \cap L(r_2)$\\ $L(r^{\{n\}})$ & $\dn$ & $L(r)^n$\\ $L(r^{\{..m\}})$ & $\dn$ & $\bigcup_{0\le i \le m}.\;L(r)^i$\\ $L(r^{\{n..\}})$ & $\dn$ & $\bigcup_{n\le i}.\;L(r)^i$\\ $L(r^{\{n..m\}})$ & $\dn$ & $\bigcup_{n\le i \le m}.\;L(r)^i$\\ $L(\sim{}r)$ & $\dn$ & $\Sigma^* - L(r)$\end{tabular}\end{center}\noindent whereby in the last clause the set $\Sigma^*$ standsfor the set of \emph{all} strings over the alphabet $\Sigma$(in the implementation the alphabet can be just what isrepresented by, say, the type \pcode{Char}). So $\sim{}r$means in effect ``all the strings that $r$ cannot match''.\medskip \noindentBe careful that your implementation of \textit{nullable} and\textit{der} satisfies for every regular expression $r$ the followingtwo properties (see also Question 3):\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 1 (Unmarked)}What is your King's email address (you will need it inQuestion 5)? Also, could you please let me know whether you area BSc / MSci and the year you are in (in case of MSci). Thanks!\subsection*{Question 2 (Unmarked)}Can you please also list all programming languages in which you havealready written programs (include only instances where you have spentat least a good working day fiddling with a program)? This is justfor my curiosity to estimate what your background is.\subsection*{Question 3}From the lectures you have seen the definitions for the functions\textit{nullable} and \textit{der} for the basic regularexpressions. Implement and \underline{write down} the rules for theextended regular expressions (see questionaire at the end).\noindentRemember your definitions have to satisfy the two properties\begin{itemize}\item $\textit{nullable}(r)$ if and only if $[]\in L(r)$\item $L(der\,c\,r)) = Der\,c\,(L(r))$\end{itemize}\noindentGiven the definitions of \textit{nullable} and \textit{der}, it iseasy to implement a regular expression matcher. Test your regularexpression matcher with (\underline{at least}) the examples:\begin{center}\def\arraystretch{1.2} \begin{tabular}{@{}r|m{3mm}|m{6mm}|m{6mm}|m{10mm}|m{6mm}|m{10mm}|m{10mm}|m{10mm}} string & $a^?$ & $\sim{}a$ & $a^{\{3\}}$ & $(a^?)^{\{3\}}$ & $a^{\{..3\}}$ & $(a^?)^{\{..3\}}$ & $a^{\{3..5\}}$ & $(a^?)^{\{3..5\}}$ \\\hline $[]$ &&&&&&& \\\hline \texttt{a} &&&&&&& \\\hline \texttt{aa} &&&&&&& \\\hline \texttt{aaa} &&&&&&& \\\hline \texttt{aaaaa} &&&&&&& \\\hline \texttt{aaaaaa}&&&&&&& \\\end{tabular}\end{center}\noindentDoes your matcher produce the expected results? Make sure youalso test corner-cases, like $a^{\{0\}}$!\subsection*{Question 4}As you can see, there are a number of explicit regular expressionsthat deal with single or several characters, for example:\begin{center}\begin{tabular}{ll} $c$ & matches a single character\\ $[c_1,c_2,\ldots,c_n]$ & matches a set of characters---for character ranges\\ $\textit{ALL}$ & matches any character\end{tabular}\end{center}\noindentThe latter is useful for matching any string (for exampleby using $\textit{ALL}^*$). In order to avoid having an explicit constructorfor each case, we can generalise all these cases and introduce a singleconstructor $\textit{CFUN}(f)$ where $f$ is a function from charactersto booleans. In Scala code this would look as follows:\begin{lstlisting}[numbers=none]abstract class Rexp...case class CFUN(f: Char => Boolean) extends Rexp \end{lstlisting}\smallskip\noindentThe idea is that the function $f$ determines which character(s)are matched, namely those where $f$ returns \texttt{true}.In this question implement \textit{CFUN} and define\begin{center}\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} $\textit{nullable}(\textit{CFUN}(f))$ & $\dn$ & $?$\\ $\textit{der}\,c\,(\textit{CFUN}(f))$ & $\dn$ & $?$\end{tabular}\end{center}\noindent in your matcher and then also give definitions for\begin{center}\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} $c$ & $\dn$ & $\textit{CFUN}(?)$\\ $[c_1,c_2,\ldots,c_n]$ & $\dn$ & $\textit{CFUN}(?)$\\ $\textit{ALL}$ & $\dn$ & $\textit{CFUN}(?)$\end{tabular}\end{center}\noindentYou can either add the constructor $CFUN$ to your implementation inQuestion 3, or you can implement this questions firstand then use $CFUN$ instead of \code{RANGE} and \code{CHAR} in Question 3.In an ideal world one would do this task first, but this might confuseyou with what you need to do in the previous question.\subsection*{Question 5}Suppose $[a\mbox{-}z0\mbox{-}9\_\,.\mbox{-}]$ stands for the regular expression\[[a,b,c,\ldots,z,0,\dots,9,\_,.,\mbox{-}]\;.\]\noindentDefine in your code 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 own emailaddress. When calculating the derivative, simplify all regularexpressions as much as possible by applying thefollowing 7 simplification rules:\begin{center}\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll}$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\ $\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\ $r \cdot \ONE$ & $\mapsto$ & $r$\\ $\ONE \cdot r$ & $\mapsto$ & $r$\\ $r + \ZERO$ & $\mapsto$ & $r$\\ $\ZERO + r$ & $\mapsto$ & $r$\\ $r + r$ & $\mapsto$ & $r$\\ \end{tabular}\end{center}\noindent Write down your simplified derivative in a readablenotation using parentheses where necessary. That means youshould use the infix notation $+$, $\cdot$, $^*$ and so on,instead of raw code.\bigskip\subsection*{Question 6}Implement the simplification rules in your regular expression matcher.Consider the regular expression $/ \cdot * \cdot(\sim{}(\textit{ALL}^* \cdot * \cdot / \cdot \textit{ALL}^*)) \cdot *\cdot /$ and decide whether the following four strings are matched bythis regular expression. Answer yes or no.\begin{enumerate}\item \texttt{"/**/"}\item \texttt{"/*foobar*/"}\item \texttt{"/*test*/test*/"}\item \texttt{"/*test/*test*/"}\end{enumerate}\subsection*{Question 7}Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be$(a^{\{19,19\}}) \cdot (a^?)$.\medskip\noindentDecide whether the following threestrings consisting of $a$s only can be matched by $(r_1^+)^+$.Similarly test them with $(r_2^+)^+$. Again answer in all six caseswith yes or no. \medskip\noindentThese are strings are meant to be entirely made up of $a$s. Be carefulwhen copy-and-pasting the strings so as to not forgetting any $a$ andto not introducing any other character.\begin{enumerate}\setcounter{enumi}{0}\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}\end{enumerate}\newpage\section*{Answers}\mbox{} \noindent\textbf{Name:}\uline{\hfill}\bigskip\noindent\textbf{BSc / MSci \hspace{2cm} Year:\uline{\hspace{2cm}}}\bigskip\noindent\textbf{Programming Languages:}\uline{\hfill}\medskip\noindent\uline{\hfill}\medskip\noindent\uline{\hfill}\medskip\noindent\uline{\hfill}\bigskip\bigskip\noindent\textbf{Question 3:}\begin{center}\def\arraystretch{1.6} \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} $\textit{nullable}([c_1,c_2,\ldots,c_n])$ & $\dn$ & \uline{\hspace{8cm}}\\ $\textit{nullable}(r^+)$ & $\dn$ & \uline{\hspace{8cm}}\\ $\textit{nullable}(r^?)$ & $\dn$ & \uline{\hspace{8cm}}\\ $\textit{nullable}(r_1 \,\&\, r_2)$ & $\dn$ & \uline{\hspace{8cm}}\\ $\textit{nullable}(r^{\{n\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ & & \uline{\hspace{8cm}}\\ $\textit{nullable}(r^{\{..m\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ & & \uline{\hspace{8cm}}\\ $\textit{nullable}(r^{\{n..\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ & & \uline{\hspace{8cm}}\\ $\textit{nullable}(r^{\{n..m\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ & & \uline{\hspace{8cm}}\\ $\textit{nullable}(\sim{}r)$ & $\dn$ & \uline{\hspace{8cm}}\\% \\\end{tabular}\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} $der\, c\, ([c_1,c_2,\ldots,c_n])$ & $\dn$ & \uline{\hspace{8cm}}\\ $der\, c\, (r^+)$ & $\dn$ & \uline{\hspace{8cm}}\\ $der\, c\, (r^?)$ & $\dn$ & \uline{\hspace{8cm}}\\ $der\, c\, (r_1 \,\&\, r_2)$ & $\dn$ & \uline{\hspace{8cm}}\\ $der\, c\, (r^{\{n\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ & & \uline{\hspace{8cm}}\\ $der\, c\, (r^{\{..m\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ & & \uline{\hspace{8cm}}\\ $der\, c\, (r^{\{n..\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ & & \uline{\hspace{8cm}}\\ $der\, c\, (r^{\{n..m\}})$ & $\dn$ & \uline{\hspace{8cm}}\\ & & \uline{\hspace{8cm}}\\ & & \uline{\hspace{8cm}}\\ $der\, c\, (\sim{}r)$ & $\dn$ & \uline{\hspace{8cm}}\end{tabular}\end{center}\bigskip\noindent\textbf{Question 4:}\begin{center}\def\arraystretch{1.6} \begin{tabular}{@ {}r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} $\textit{nullable}(CFUN(f))$ & $\dn$ & \uline{\hspace{8cm}}\\ \\ $der\, c\, (CFUN(f))$ & $\dn$ & \uline{\hspace{8cm}}\\ & & \uline{\hspace{8cm}}\\ \\ \\ $c$ & $\dn$ & \textit{CFUN}(\uline{\hspace{7cm}})\medskip\\ $[c_1,c_2,\ldots,c_n]$ & $\dn$ & \textit{CFUN}(\uline{\hspace{7cm}})\medskip\\ $\textit{ALL}$ & $\dn$ & \textit{CFUN}(\uline{\hspace{7cm}})\medskip\\\end{tabular}\end{center}\newpage\noindent\textbf{Question 5 (`mathematical' notation):}\noindent\uline{\hfill}\medskip\noindent\uline{\hfill}\medskip\noindent\uline{\hfill}\medskip\noindent\uline{\hfill}\medskip\noindent\uline{\hfill}\bigskip\bigskip\noindent\textbf{Question 6:}\medskip\noindent\textbf{1)}\; Yes / No\qquad\textbf{2)}\; Yes / No\qquad\textbf{3)}\; Yes / No\qquad\textbf{4)}\; Yes / No\bigskip\bigskip\noindent\textbf{Question 7:}\medskip\def\arraystretch{1.5}\begin{tabular}{l|c|c} & $\quad{}r_1\quad$ & $\quad{}r_2\quad$\\\hline 1. & & \\\hline 2. & & \\\hline 3. & & \\\end{tabular}\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: