--- a/cws/main_cw03.tex Mon Nov 10 16:24:46 2025 +0000
+++ b/cws/main_cw03.tex Thu Nov 13 17:44:58 2025 +0000
@@ -7,6 +7,8 @@
\usepackage{pgf}
\usepackage{pgfplots}
\usepackage{stackengine}
+\usepackage{scalerel}
+\DeclareMathOperator*{\amp}{\scalerel*{\&}{\sum}}
%% \usepackage{accents}
\newcommand\barbelow[1]{\stackunder[1.2pt]{#1}{\raisebox{-4mm}{\boldmath$\uparrow$}}}
@@ -119,7 +121,7 @@
% BF IDE
% https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5
-\section*{Main Part 3 (Scala, 7 Marks)}
+\section*{Main Part 3 (Scala, 6 Marks)}
\mbox{}\hfill\textit{``Java is the most distressing thing to happen to computing since MS-DOS.''}\smallskip\\
\mbox{}\hfill\textit{ --- Alan Kay, the inventor of object-oriented programming}\bigskip\medskip
@@ -144,7 +146,7 @@
This Scala assignment comes with a reference implementation in form of
a \texttt{jar}-file. This allows you to run any test cases on your own
-computer. For example you can call \texttt{scala-cli} on the command
+computer. For example you can call \texttt{scala} on the command
line with the option \texttt{--extra-jars re.jar} and then query any function
from the \texttt{re.scala} template file. As usual you have to prefix
the calls with \texttt{M3} or import this object. Since some tasks
@@ -155,7 +157,7 @@
\begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small]
-$ scala-cli --extra-jars re.jar
+$ scala --extra-jars re.jar
scala> import M3._
scala> for (i <- 0 to 5000000 by 500000) {
println(s"$i: ${time_needed(2, matcher(EVIL, "a" * i))}")
@@ -192,9 +194,11 @@
& $|$ & $\ONE$ & can only match the empty string\\
& $|$ & $c$ & can match a single character (in this case $c$)\\
& $|$ & $r_1 + r_2$ & can match a string either with $r_1$ or with $r_2$\\
- & $|$ & $r_1\cdot r_2$ & can match the first part of a string with $r_1$ and\\
+ & $|$ & $r_1\cdot r_2$ & can match the first part of a string with $r_1$ and\\
& & & then the second part with $r_2$\\
+ & $|$ & $r_1 \,\&\, r_2$ & has to match a string with both $r_1$ and $r_2$\\
& $|$ & $r^*$ & can match a string with zero or more copies of $r$\\
+ & $|$ & $r^{\{n\}}$ & can match a string with exactly n copies of $r$\\
\end{tabular}
\end{center}
@@ -204,7 +208,7 @@
are endlessly useful for searching, editing and analysing data in all
sorts of places (for example analysing network traffic in order to
detect security breaches). However, you need to be fast, otherwise you
-will stumble over problems such as recently reported at
+will stumble over problems such as reported in
{\small
\begin{itemize}
@@ -231,27 +235,14 @@
$\ZERO$ & $\mapsto$ & \texttt{ZERO}\\
$\ONE$ & $\mapsto$ & \texttt{ONE}\\
$c$ & $\mapsto$ & \texttt{CHAR(c)}\\
- $\sum rs$ & $\mapsto$ & \texttt{ALTs(rs)}\\
$r_1 + r_2$ & $\mapsto$ & \texttt{ALT(r1, r2)} & \texttt{r1 | r2}\\
- $\prod rs$ & $\mapsto$ & \texttt{SEQs(rs)}\\
$r_1 \cdot r_2$ & $\mapsto$ & \texttt{SEQ(r1, r2)} & \texttt{r1 $\sim$ r2}\\
- $r^*$ & $\mapsto$ & \texttt{STAR(r)} & \texttt{r.\%}
+ $r_1 \,\&\, r_2$ & $\mapsto$ & \texttt{AND(r1, r2)}\\
+ $r^*$ & $\mapsto$ & \texttt{STAR(r)} & \texttt{r.\%}\\
+ $r^{\{n\}}$ & $\mapsto$ & \texttt{REP(r, n)} &
\end{tabular}
\end{center}
-\noindent
-The alternative regular expression comes in two versions: one is
-binary (+ / \texttt{ALT}) and the other is n-ary ($\sum$ /
-\texttt{ALTs}). The latter takes a list of regular expressions as
-argument. In what follows we shall use $rs$ to stand for lists of
-regular expressions. When the list is empty, we shall write $\sum\,[]$;
-if it is non-empty, we sometimes write $\sum\,[r_1,..., r_n]$.
-The binary alternative can be seen as an abbreviation,
-that is $r_1 + r_2 \dn \sum\,[r_1, r_2]$. As a result we can ignore the
-binary version and only implement the n-ary alternative. Similarly
-the sequence regular expression is only implemented with lists and the
-binary version can be obtained by defining $r_1 \cdot r_2 \dn \prod\,[r_1, r_2]$.
-
\begin{itemize}
\item[(1)] Implement a function, called \textit{nullable}, by
recursion over regular expressions. This function tests whether a
@@ -265,9 +256,14 @@
$\textit{nullable}(\ZERO)$ & $\dn$ & $\textit{false}$\\
$\textit{nullable}(\ONE)$ & $\dn$ & $\textit{true}$\\
$\textit{nullable}(c)$ & $\dn$ & $\textit{false}$\\
-$\textit{nullable}(\sum rs)$ & $\dn$ & $\exists r \in rs.\;\textit{nullable}(r)$\\
-$\textit{nullable}(\prod rs)$ & $\dn$ & $\forall r\in rs.\;\textit{nullable}(r)$\\
+$\textit{nullable}(r_1 + r_2)$ & $\dn$ & $\textit{nullable}(r_1) \vee \textit{nullable}(r_2)$\\
+$\textit{nullable}(r_1 \cdot r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge \textit{nullable}(r_2)$\\
+$\textit{nullable}(r_1 \& r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge \textit{nullable}(r_2)$\\
$\textit{nullable}(r^*)$ & $\dn$ & $\textit{true}$\\
+$\textit{nullable}(r^{\{n\}})$ & $\dn$ &
+$\begin{cases}\textit{true} & n = 0\\
+\textit{nullable}(r) & \textit{otherwise}
+\end{cases}$\\
\end{tabular}
\end{center}~\hfill[0.5 Marks]
@@ -281,131 +277,175 @@
$\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\
$\textit{der}\;c\;(\ONE)$ & $\dn$ & $\ZERO$\\
$\textit{der}\;c\;(d)$ & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\
-$\textit{der}\;c\;(\sum\;[r_1,..,r_n])$ & $\dn$ & $\sum\;[\textit{der}\;c\;r_1,..,\textit{der}\;c\;r_n]$\\
-$\textit{der}\;c\;(\prod\;[])$ & $\dn$ & $\ZERO$\\
-$\textit{der}\;c\;(\prod\;r\!::\!rs)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r)$\\
- & & $\textit{then}\;(\prod\;(\textit{der}\;c\;r)\!::\!rs) + (\textit{der}\;c\;(\prod rs))$\\
- & & $\textit{else}\;(\prod\;(\textit{der}\;c\;r)\!::\! rs)$\\
+$\textit{der}\;c\;(r_1 + r_2)$ & $\dn$ & $(\textit{der}\;c\;r_1) + (\textit{der}\;c\;r_2)$\\
+$\textit{der}\;c\;(r_1 \& r_2)$ & $\dn$ & $(\textit{der}\;c\;r_1) \,\&\, (\textit{der}\;c\;r_2)$\\
+$\textit{der}\;c\;(r_1 \cdot r_2)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r_1)$\\
+ & & $\textit{then}\;(\textit{der}\;c\;r_1)\cdot r_2 \,+\, (\textit{der}\;c\;r_2)$\\
+ & & $\textit{else}\;(\textit{der}\;c\;r_1)\cdot r_2$\\
$\textit{der}\;c\;(r^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\
+$\textit{der}\;c\;(r^{\{n\}})$ & $\dn$ &
+$\begin{cases}\ZERO & n = 0\\
+(der\,c\,r)\cdot (r^{\{n-1\}}) & \textit{otherwise}
+\end{cases}$\\
\end{tabular}
\end{center}
-\mbox{}\hfill\mbox{[1 Mark]}
+\mbox{}\hfill\mbox{[1.5 Marks]}
+
+% \item[(3)] We next want to simplify regular expressions: essentially
+% we want to remove $\ZERO$ in regular expressions like $r + \ZERO$
+% and $\ZERO + r$. However, our n-ary alternative takes a list of
+% regular expressions as argument, and we therefore need a more general
+% ``denesting'' function, which deletes $\ZERO$s and ``spills out'' nested
+% $\sum$s. This function, called \texttt{denest}, should analyse a
+% list of regular expressions, say $rs$, as follows:
-\item[(3)] We next want to simplify regular expressions: essentially
- we want to remove $\ZERO$ in regular expressions like $r + \ZERO$
- and $\ZERO + r$. However, our n-ary alternative takes a list of
- regular expressions as argument, and we therefore need a more general
- ``denesting'' function, which deletes $\ZERO$s and ``spills out'' nested
- $\sum$s. This function, called \texttt{denest}, should analyse a
- list of regular expressions, say $rs$, as follows:
+% \begin{center}
+% \begin{tabular}{lllll}
+% 1) &$rs = []$ & $\dn$ & $[]$ & (empty list)\\
+% 2) &$rs = \ZERO :: rest$ & $\dn$ & $\texttt{denest}\;rest$ & (throw away $\ZERO$)\\
+% 3) &$rs = (\sum rs) :: rest$ & $\dn$ & $rs ::: \texttt{denest}\;rest$ & (spill out $\sum$)\\
+% 4) &$rs = r :: rest$ & $\dn$ & $r :: \texttt{denest}\;rest$ & (otherwise)\\
+% \end{tabular}
+% \end{center}
+
+% The first clause states that empty lists cannot be further
+% denested. The second removes the first $\ZERO$ from the list and recurses.
+% The third is when the first regular expression is an \texttt{ALTs}, then
+% the content of this alternative should be spilled out and appended
+% with the denested rest of the list. The last case is for all other
+% cases where the head of the list is not $\ZERO$ and not an \texttt{ALTs},
+% then we just keep the head of the list and denest the rest.\\
+% \mbox{}\hfill\mbox{[1 Mark]}
+
+\item[(3)] Implement the function \textit{simp}, which recursively
+ traverses a regular expression, and on the way up simplifies every
+ regular expression on the left (see below) to the regular expression
+ on the right, except it does not simplify inside ${}^*$ and ${}^{\{n\}}$-regular
+ expressions.
\begin{center}
- \begin{tabular}{lllll}
- 1) &$rs = []$ & $\dn$ & $[]$ & (empty list)\\
- 2) &$rs = \ZERO :: rest$ & $\dn$ & $\texttt{denest}\;rest$ & (throw away $\ZERO$)\\
- 3) &$rs = (\sum rs) :: rest$ & $\dn$ & $rs ::: \texttt{denest}\;rest$ & (spill out $\sum$)\\
- 4) &$rs = r :: rest$ & $\dn$ & $r :: \texttt{denest}\;rest$ & (otherwise)\\
- \end{tabular}
- \end{center}
-
- The first clause states that empty lists cannot be further
- denested. The second removes the first $\ZERO$ from the list and recurses.
- The third is when the first regular expression is an \texttt{ALTs}, then
- the content of this alternative should be spilled out and appended
- with the denested rest of the list. The last case is for all other
- cases where the head of the list is not $\ZERO$ and not an \texttt{ALTs},
- then we just keep the head of the list and denest the rest.\\
- \mbox{}\hfill\mbox{[1 Mark]}
-
-\item[(4)] Implement the function \texttt{flts} which flattens our
- n-ary sequence regular expression $\prod$. Like \texttt{denest}, this
- function is intended to delete $\ONE$s and spill out nested $\prod$s.
- Unfortunately, there is a special case to do with $\ZERO$: If this function encounters a $\ZERO$, then
- the whole ``product'' should be $\ZERO$. The problem is that the $\ZERO$ can be anywhere
- inside the list. The easiest way to implement this function is therefore by using an
- accumulator, which when called is set to \texttt{Nil}. This means \textit{flts} takes
- two arguments (which are both lists of regular expressions)
-
- \[
- \texttt{flts}\;rs\;acc
- \]
-
- This function analyses the list $rs$ as follows
-
- \begin{center}
- \begin{tabular}{@{}lllll@{}}
- 1) &$rs = []$ & $\dn$ & $acc$ & (empty list)\\
- 2) &$rs = \ZERO :: rest$ & $\dn$ & $[\ZERO]$ & (special case for $\ZERO$)\\
- 3) &$rs = \ONE :: rest$ & $\dn$ & $\texttt{flts}\,rest\,acc$ & (throw away $\ONE$)\\
- 4) &$rs = (\prod rs) :: rest$ & $\dn$ & $\texttt{flts}\;rest\,(acc ::: rs)$ & (spill out $\prod$)\\
- 5) &$rs = r :: rest$ & $\dn$ & $\texttt{flts}\;rest\,(acc ::: [r])$& (otherwise)\\
- \end{tabular}
+\begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}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$\\
+$r \,\&\, \ZERO$ & $\mapsto$ & $\ZERO$\\
+$\ZERO \,\&\, r$ & $\mapsto$ & $\ZERO$\\
+$r \,\&\, r$ & $\mapsto$ & $r$\\
+\end{tabular}
\end{center}
- In the first case we just return whatever has accumulated in
- $acc$. In the fourth case we spill out the $rs$ by appending the
- $rs$ to the end of the accumulator. Similarly in the last case we
- append the single regular expression $r$ to the end of the
- accumulator. I let you think why you have to add it to the end. \mbox{}\hfill\mbox{[1 Mark]}
+ For example the regular expression
+ \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \,\&\, (r_4 \cdot \ZERO)\]
+
+ simplifies to just $r_1$. \textbf{Hint:} Regular expressions can be
+ seen as trees and there are several methods for traversing
+ trees. One of them corresponds to the inside-out traversal, which is also
+ sometimes called post-order tra\-versal: you traverse inside the
+ tree and on the way up you apply simplification rules.
+ \textbf{Another Hint:}
+ Remember numerical expressions from school times---there you had expressions
+ like $u + \ldots + (1 \cdot x) - \ldots (z + (y \cdot 0)) \ldots$
+ and simplification rules that looked very similar to rules
+ above. You would simplify such numerical expressions by replacing
+ for example the $y \cdot 0$ by $0$, or $1\cdot x$ by $x$, and then
+ look whether more rules are applicable. If you organise the
+ simplification in an inside-out fashion, it is always clear which
+ simplification should be applied next.\hfill[2 Marks]
+
-\item[(5)] Before we can simplify regular expressions, we need what is often called
- \emph{smart constructors} for $\sum$ and $\prod$. While the ``normal'' constructors
- \texttt{ALTs} and \texttt{SEQs} give us alternatives and sequences, respectively, \emph{smart}
- constructors might return something different depending on what list of regular expressions
- they are given as argument.
+% \item[(4)] Implement the function \texttt{flts} which flattens our
+% n-ary sequence regular expression $\prod$. Like \texttt{denest}, this
+% function is intended to delete $\ONE$s and spill out nested $\prod$s.
+% Unfortunately, there is a special case to do with $\ZERO$: If this function encounters a $\ZERO$, then
+% the whole ``product'' should be $\ZERO$. The problem is that the $\ZERO$ can be anywhere
+% inside the list. The easiest way to implement this function is therefore by using an
+% accumulator, which when called is set to \texttt{Nil}. This means \textit{flts} takes
+% two arguments (which are both lists of regular expressions)
+
+% \[
+% \texttt{flts}\;rs\;acc
+% \]
+
+% This function analyses the list $rs$ as follows
+
+% \begin{center}
+% \begin{tabular}{@{}lllll@{}}
+% 1) &$rs = []$ & $\dn$ & $acc$ & (empty list)\\
+% 2) &$rs = \ZERO :: rest$ & $\dn$ & $[\ZERO]$ & (special case for $\ZERO$)\\
+% 3) &$rs = \ONE :: rest$ & $\dn$ & $\texttt{flts}\,rest\,acc$ & (throw away $\ONE$)\\
+% 4) &$rs = (\prod rs) :: rest$ & $\dn$ & $\texttt{flts}\;rest\,(acc ::: rs)$ & (spill out $\prod$)\\
+% 5) &$rs = r :: rest$ & $\dn$ & $\texttt{flts}\;rest\,(acc ::: [r])$& (otherwise)\\
+% \end{tabular}
+% \end{center}
+
+% In the first case we just return whatever has accumulated in
+% $acc$. In the fourth case we spill out the $rs$ by appending the
+% $rs$ to the end of the accumulator. Similarly in the last case we
+% append the single regular expression $r$ to the end of the
+% accumulator. I let you think why you have to add it to the end. \mbox{}\hfill\mbox{[1 Mark]}
- \begin{center}
- \begin{tabular}{@{}c@{\hspace{9mm}}c@{}}
- \begin{tabular}{l@{\hspace{2mm}}l@{\hspace{1mm}}ll}
- & $\sum^{smart}$\smallskip\\
- 1) & $rs = []$ & $\dn$ & $\ZERO$\\
- 2) & $rs = [r]$ & $\dn$ & $r$\\ \\
- 3) & otherwise & $\dn$ & $\sum\,rs$
- \end{tabular} &
- \begin{tabular}{l@{\hspace{2mm}}l@{\hspace{1mm}}ll}
- & $\prod^{smart}$\smallskip\\
- 1) & $rs = []$ & $\dn$ & $\ONE$\\
- 2a) & $rs = [\ZERO]$ & $\dn$ & $\ZERO$\\
- 2b) & $rs = [r]$ & $\dn$ & $r$\\
- 3) & otherwise & $\dn$ & $\prod\,rs$
- \end{tabular}
- \end{tabular}
- \end{center}
- \mbox{}\hfill\mbox{[0.5 Marks]}
+% \item[(5)] Before we can simplify regular expressions, we need what is often called
+% \emph{smart constructors} for $\sum$ and $\prod$. While the ``normal'' constructors
+% \texttt{ALTs} and \texttt{SEQs} give us alternatives and sequences, respectively, \emph{smart}
+% constructors might return something different depending on what list of regular expressions
+% they are given as argument.
+
+% \begin{center}
+% \begin{tabular}{@{}c@{\hspace{9mm}}c@{}}
+% \begin{tabular}{l@{\hspace{2mm}}l@{\hspace{1mm}}ll}
+% & $\sum^{smart}$\smallskip\\
+% 1) & $rs = []$ & $\dn$ & $\ZERO$\\
+% 2) & $rs = [r]$ & $\dn$ & $r$\\ \\
+% 3) & otherwise & $\dn$ & $\sum\,rs$
+% \end{tabular} &
+% \begin{tabular}{l@{\hspace{2mm}}l@{\hspace{1mm}}ll}
+% & $\prod^{smart}$\smallskip\\
+% 1) & $rs = []$ & $\dn$ & $\ONE$\\
+% 2a) & $rs = [\ZERO]$ & $\dn$ & $\ZERO$\\
+% 2b) & $rs = [r]$ & $\dn$ & $r$\\
+% 3) & otherwise & $\dn$ & $\prod\,rs$
+% \end{tabular}
+% \end{tabular}
+% \end{center}
+% \mbox{}\hfill\mbox{[0.5 Marks]}
-\item[(6)] Implement the function \textit{simp}, which recursively
- traverses a regular expression, and on the way up simplifies every
- regular expression on the left (see below) to the regular expression
- on the right, except it does not simplify inside ${}^*$-regular
- expressions and also does not simplify $\ZERO$, $\ONE$ and characters.
+% \item[(6)] Implement the function \textit{simp}, which recursively
+% traverses a regular expression, and on the way up simplifies every
+% regular expression on the left (see below) to the regular expression
+% on the right, except it does not simplify inside ${}^*$-regular
+% expressions and also does not simplify $\ZERO$, $\ONE$ and characters.
- \begin{center}
- \begin{tabular}{@{}l@{\hspace{3mm}}c@{\hspace{3mm}}ll@{}}
- LHS: & & RHS:\smallskip\\
-$\sum\;[r_1,..,r_n]$ & $\mapsto$ & $\sum^{smart}\;(\texttt{(denest + distinct)}[simp(r_1),..,simp(r_n)])$\\
- $\prod\;[r_1,..,r_n]$ & $\mapsto$ & $\prod^{smart}\;(\texttt{(flts)}[simp(r_1),..,simp(r_n)])$\\
- $r$ & $\mapsto$ & $r$ \quad (all other cases)
-\end{tabular}
-\end{center}
+% \begin{center}
+% \begin{tabular}{@{}l@{\hspace{3mm}}c@{\hspace{3mm}}ll@{}}
+% LHS: & & RHS:\smallskip\\
+% $\sum\;[r_1,..,r_n]$ & $\mapsto$ & $\sum^{smart}\;(\texttt{(denest + distinct)}[simp(r_1),..,simp(r_n)])$\\
+% $\prod\;[r_1,..,r_n]$ & $\mapsto$ & $\prod^{smart}\;(\texttt{(flts)}[simp(r_1),..,simp(r_n)])$\\
+% $r$ & $\mapsto$ & $r$ \quad (all other cases)
+% \end{tabular}
+% \end{center}
-The first case is as follows: first apply $simp$ to all regular
-expressions $r_1,.. ,r_n$; then denest the resulting list using
-\texttt{denest}; after that remove all duplicates in this list (this can be
-done in Scala using the function
-\texttt{\_.distinct}). Finally, you end up with a list of (simplified)
-regular expressions; apply the smart constructor $\sum^{smart}$ to this list.
-Similarly in the $\prod$ case: simplify first all regular
-expressions $r_1,.. ,r_n$; then flatten the resulting list using \texttt{flts} and apply the
-smart constructor $\prod^{smart}$ to the result. In all other cases, just return the
-input $r$ as is.
+% The first case is as follows: first apply $simp$ to all regular
+% expressions $r_1,.. ,r_n$; then denest the resulting list using
+% \texttt{denest}; after that remove all duplicates in this list (this can be
+% done in Scala using the function
+% \texttt{\_.distinct}). Finally, you end up with a list of (simplified)
+% regular expressions; apply the smart constructor $\sum^{smart}$ to this list.
+% Similarly in the $\prod$ case: simplify first all regular
+% expressions $r_1,.. ,r_n$; then flatten the resulting list using \texttt{flts} and apply the
+% smart constructor $\prod^{smart}$ to the result. In all other cases, just return the
+% input $r$ as is.
- For example the regular expression
- \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\]
+% For example the regular expression
+% \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\]
- simplifies to just $r_1$. \mbox{}\hfill\mbox{[1 Mark]}
+% simplifies to just $r_1$. \mbox{}\hfill\mbox{[1 Mark]}
-\item[(7)] Implement two functions: The first, called \textit{ders},
+\item[(4)] Implement two functions: The first, called \textit{ders},
takes a list of characters and a regular expression as arguments, and
builds the derivative w.r.t.~the list as follows:
@@ -428,19 +468,19 @@
true for the regular expression $(a\cdot b)\cdot c$ and the string
$abc$, but false if you give it the string $ab$. \hfill[0.5 Mark]
-\item[(8)] Implement a function, called \textit{size}, by recursion
+\item[(5)] Implement a function, called \textit{size}, by recursion
over regular expressions. If a regular expression is seen as a tree,
then \textit{size} should return the number of nodes in such a
tree. Therefore this function is defined as follows:
\begin{center}
-\begin{tabular}{lcl}
+\begin{tabular}{lcll}
$\textit{size}(\ZERO)$ & $\dn$ & $1$\\
$\textit{size}(\ONE)$ & $\dn$ & $1$\\
$\textit{size}(c)$ & $\dn$ & $1$\\
-$\textit{size}(\sum\,[r_1,..,r_n]$ & $\dn$ & $1 + \textit{size}(r_1) + ... + \textit{size}(r_n)$\\
-$\textit{size}(\prod\,[r_1,..,r_n]$ & $\dn$ & $1 + \textit{size}(r_1) + ... + \textit{size}(r_n)$\\
+$\textit{size}(r_1 \,?\, r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$ & where $? \in \{\cdot, +, \&\}$\\
$\textit{size}(r^*)$ & $\dn$ & $1 + \textit{size}(r)$\\
+$\textit{size}(r^{\{n\}})$ & $\dn$ & $1 + \textit{size}(r)$\\
\end{tabular}
\end{center}
@@ -450,7 +490,7 @@
taking the derivative, but simplify the result. The sizes
are given in \texttt{re.scala}. \hfill[0.5 Marks]
-\item[(9)] You do not have to implement anything specific under this
+\item[(6)] You do not have to implement anything specific under this
task. The purpose here is that you will be marked for some ``power''
test cases. For example can your matcher decide within 30 seconds
whether the regular expression $(a^*)^*\cdot b$ matches strings of the
@@ -469,7 +509,7 @@
\subsection*{Background}
Although easily implementable in Scala (ok maybe the \texttt{simp} functions and
-the constructors \texttt{ALTs}/\texttt{SEQs} needs a bit more thinking), the idea behind the
+the constructors \texttt{ALT}/\texttt{SEQ}/\texttt{AND} needs a bit more thinking), the idea behind the
derivative function might not so easy to be seen. To understand its
purpose better, assume a regular expression $r$ can match strings of
the form $c\!::\!cs$ (that means strings which start with a character
@@ -567,7 +607,7 @@
axis lines=left,
width=6cm,
height=5.5cm,
- legend entries={Java 9},
+ legend entries={Java 9 and above},
legend pos=north west]
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java9.data};
\end{axis}