pep-material: comparison cws/main

equal deleted inserted replaced

-:6e93040e3378
+:cdfa6a293453
 \begin{document}
 % BF IDE
 % https://www.microsoft.com/en-us/p/brainf-ck/9nblgggzhvq5
-\section*{Main Part 3 (Scala, 6 Marks)}
+\section*{Main Part 3 (Scala, 7 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
 \noindent
 will stumble over problems such as recently reported at
 {\small
 \begin{itemize}
 \item[$\bullet$] \url{https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019}
-\item[$\bullet$] \url{https://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}
+\item[$\bullet$] \texttt{\href{https://web.archive.org/web/20160801163029/https://www.stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}{https://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016}}
 \item[$\bullet$] \url{https://vimeo.com/112065252}
 \item[$\bullet$] \url{https://davidvgalbraith.com/how-i-fixed-atom}
 \end{itemize}}
 % Knowing how to match regular expressions and strings will let you
 \subsubsection*{Tasks (file re.scala)}
 The file \texttt{re.scala} has already a definition for regular
-expressions and also defines some handy shorthand notation for
+expressions and also defines some handy shorthand notation for regular
-regular expressions. The notation in this document matches up
+expressions. The notation in this coursework description matches up
-with the code in the file as follows:
+with the code as follows:
 \begin{center}
 \begin{tabular}{rcl@{\hspace{10mm}}l}
 & & code: & shorthand:\smallskip \\
 $\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.\%}
 \end{tabular}
 \end{center}
 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.
+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
 regular expression can match the empty string. This means given a
-regular expression it either returns true or false. The function
+regular expression, it either returns true or false. The function
 \textit{nullable}
 is defined as follows:
 \begin{center}
 \begin{tabular}{lcl}
 $\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}(r_1 \cdot r_2)$ & $\dn$ & $\textit{nullable}(r_1) \wedge \textit{nullable}(r_2)$\\
+$\textit{nullable}(\prod rs)$ & $\dn$ & $\forall r\in rs.\;\textit{nullable}(r)$\\
 $\textit{nullable}(r^*)$ & $\dn$ & $\textit{true}$\\
 \end{tabular}
 \end{center}~\hfill[0.5 Marks]
 \item[(2)] Implement a function, called \textit{der}, by recursion over
 \begin{tabular}{lcl}
 $\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\;(r_1 \cdot r_2)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r_1)$\\
+$\textit{der}\;c\;(\prod\;[])$ & $\dn$ & $\ZERO$\\
-& & $\textit{then}\;((\textit{der}\;c\;r_1)\cdot r_2) + (\textit{der}\;c\;r_2)$\\
+$\textit{der}\;c\;(\prod\;r\!::\!rs)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r)$\\
-& & $\textit{else}\;(\textit{der}\;c\;r_1)\cdot r_2$\\
+& & $\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^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\
 \end{tabular}
 \end{center}
-For example given the regular expression $r = (a \cdot b) \cdot c$, the derivatives
-w.r.t.~the characters $a$, $b$ and $c$ are
-\begin{center}
-\begin{tabular}{lcll}
-$\textit{der}\;a\;r$ & $=$ & $(\ONE \cdot b)\cdot c$ & \quad($= r'$)\\
-$\textit{der}\;b\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$\\
-$\textit{der}\;c\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$
-\end{tabular}
-\end{center}
-Let $r'$ stand for the first derivative, then taking the derivatives of $r'$
-w.r.t.~the characters $a$, $b$ and $c$ gives
-\begin{center}
-\begin{tabular}{lcll}
-$\textit{der}\;a\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$ \\
-$\textit{der}\;b\;r'$ & $=$ & $((\ZERO \cdot b) + \ONE)\cdot c$ & \quad($= r''$)\\
-$\textit{der}\;c\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$
-\end{tabular}
-\end{center}
-One more example: Let $r''$ stand for the second derivative above,
-then taking the derivatives of $r''$ w.r.t.~the characters $a$, $b$
-and $c$ gives
-\begin{center}
-\begin{tabular}{lcll}
-$\textit{der}\;a\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$ \\
-$\textit{der}\;b\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$\\
-$\textit{der}\;c\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ONE$ &
-(is $\textit{nullable}$)
-\end{tabular}
-\end{center}
-Note, the last derivative can match the empty string, that is it is \textit{nullable}.\\
 \mbox{}\hfill\mbox{[1 Mark]}
 \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, we therefore need a more general
+regular expressions as argument, and we therefore need a more general
-``flatten'' function, called \texttt{flts}. This function should
+``denesting'' function, which deletes $\ZERO$s and ``spills out'' nested
-analyse a list of regular expressions, say $rs$, as follows:
+$\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$ & $\textrm{flatten}\;rest$\\
+2) &$rs = \ZERO :: rest$     & $\dn$ & $\texttt{denest}\;rest$ & (throw away $\ZERO$)\\
-3) &$rs = (\sum rs_1) :: rest$ & $\dn$ & $rs_1 ::: \textrm{flatten}\;rest$\\
+3) &$rs = (\sum rs) :: rest$ & $\dn$ & $rs ::: \texttt{denest}\;rest$ & (spill out $\sum$)\\
-4) &$rs = r :: rest$         & $\dn$ & $r :: \textrm{flatten}\;rest$ & (otherwise)\\
+4) &$rs = r :: rest$         & $\dn$ & $r :: \texttt{denest}\;rest$ & (otherwise)\\
 \end{tabular}
 \end{center}
 The first clause states that empty lists cannot be further
-flattened. The second removes the first $\ZERO$ from the list and recurses.
+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 flattened rest of the list. The last case is for all other
+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 flatten the rest.
+then we just keep the head of the list and denest the rest.\\
 \mbox{}\hfill\mbox{[1 Mark]}
-\item[(4)] Implement the function \textit{simp}, which recursively
+\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 the ``end'' is needed. \mbox{}\hfill\mbox{[1 Mark]}
+\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.
+expressions and also does not simplify $\ZERO$, $\ONE$ and characters.
 \begin{center}
-\begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll}
+\begin{tabular}{@{}l@{\hspace{3mm}}c@{\hspace{3mm}}ll@{}}
-$r \cdot \ZERO$ & $\mapsto$ & $\ZERO$\\
+LHS: & & RHS:\smallskip\\
-$\ZERO \cdot r$ & $\mapsto$ & $\ZERO$\\
+$\sum\;[r_1,..,r_n]$ & $\mapsto$ & $\sum^{smart}\;(\texttt{(denest + distinct)}[simp(r_1),..,simp(r_n)])$\\
-$r \cdot \ONE$ & $\mapsto$ & $r$\\
+$\prod\;[r_1,..,r_n]$ & $\mapsto$ & $\prod^{smart}\;(\texttt{(flts)}[simp(r_1),..,simp(r_n)])$\\
-$\ONE \cdot r$ & $\mapsto$ & $r$\\
+$r$ & $\mapsto$ & $r$ \quad (all other cases)
-$\sum\;[r_1,..,r_n]$ & $\mapsto$ & $\sum\;(\texttt{(flts + distinct)}[simp(r_1),..,simp(r_n)])$\\
 \end{tabular}
 \end{center}
-The last case is as follows: first apply $simp$ to all regular
+The first case is as follows: first apply $simp$ to all regular
-expressions $r_1,.. ,r_n$; then flatten the resulting list using
+expressions $r_1,.. ,r_n$; then denest the resulting list using
-\texttt{flts}; finally remove all duplicates in this list (this can be
+\texttt{denest}; after that remove all duplicates in this list (this can be
 done in Scala using the function
-\texttt{\_.distinct}). When you perform these
+\texttt{\_.distinct}). Finally, you end up with a list of (simplified)
-operations, you end up with three cases, namely where the list is
+regular expressions; apply the smart constructor $\sum^{smart}$ to this list.
-empty, contains a single element and ``otherwise''. These cases
+Similarly in the $\prod$ case: simplify first all regular
-should be processed as follows
+expressions $r_1,.. ,r_n$; then flatten the resulting list using \texttt{flts} and apply the
-\begin{center}
+smart constructor $\prod^{smart}$ to the result. In all other cases, just return the
-\begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll}
+input $r$ as is.
-$\sum\;[]$ & $\mapsto$ & $\ZERO$\\
-$\sum\;[r]$ & $\mapsto$ & $r$\\
-$\sum\;rs$ & $\mapsto$ & $\sum\;rs$ & ``otherwise''\\
-\end{tabular}
-\end{center}
 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$. \textbf{Hint:} Regular expressions can be
+simplifies to just $r_1$. \mbox{}\hfill\mbox{[1 Mark]}
-seen as trees and there are several methods for traversing
-trees. One of them corresponds to the inside-out traversal, which is
+\item[(7)] Implement two functions: The first, called \textit{ders},
-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 regard regular expressions as
-trees and if you organise the simplification in an inside-out
-fashion, it is always clear which simplification should be applied
-next.\mbox{}\hfill\mbox{[1 Mark]}
-\item[(5)] 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:
 \begin{center}
 \begin{tabular}{lcl}
 $\textit{ders}\;(Nil)\;r$ & $\dn$ & $r$\\
 $\textit{ders}\;(c::cs)\;r$  & $\dn$ &
-$\textit{ders}\;cs\;(\textit{simp}(\textit{der}\;c\;r))$\\
+$\textit{ders}\;cs\;(\textit{simp}\,(\textit{der}\;c\;r))$\\
 \end{tabular}
 \end{center}
 Note that this function is different from \textit{der}, which only
 takes a single character.
 regular expression as arguments. It builds first the derivatives
 according to \textit{ders} and after that tests whether the resulting
 derivative regular expression can match the empty string (using
 \textit{nullable}).  For example the \textit{matcher} will produce
 true for the regular expression $(a\cdot b)\cdot c$ and the string
-$abc$, but false if you give it the string $ab$. \hfill[1 Mark]
+$abc$, but false if you give it the string $ab$. \hfill[0.5 Mark]
-\item[(6)] Implement a function, called \textit{size}, by recursion
+\item[(8)] 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}
 $\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}(r_1 \cdot r_2)$ & $\dn$ & $1 + \textit{size}(r_1) + \textit{size}(r_2)$\\
+$\textit{size}(\prod\,[r_1,..,r_n]$ & $\dn$ & $1 + \textit{size}(r_1) + ... + \textit{size}(r_n)$\\
 $\textit{size}(r^*)$ & $\dn$ & $1 + \textit{size}(r)$\\
 \end{tabular}
 \end{center}
 You can use \textit{size} in order to test how much the ``evil'' regular
 expression $(a^*)^* \cdot b$ grows when taking successive derivatives
 according the letter $a$ without simplification and then compare it to
 taking the derivative, but simplify the result.  The sizes
 are given in \texttt{re.scala}. \hfill[0.5 Marks]
-\item[(7)] You do not have to implement anything specific under this
+\item[(9)] 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
 form $aaa\ldots{}aaaa$, for say 1 Million $a$'s. And does simplification
 simplify the regular expression
 \end{itemize}
 \subsection*{Background}
 Although easily implementable in Scala (ok maybe the \texttt{simp} functions and
-\texttt{ALTs} needs a bit more thinking), the idea behind the
+the constructors \texttt{ALTs}/\texttt{SEQs} 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
 $c$ and have some rest, or tail, $cs$). If you take the derivative of
 $r$ with respect to the character $c$, then you obtain a regular
 where $b$ is chopped off). If you finally build the derivative of this
 according $c$, that is
 $\textit{der}\;c\;(\textit{der}\;b\;(\textit{der}\;a\;r))$, you obtain
 a regular expression that can match the empty string. You can test
 whether this is indeed the case using the function nullable, which is
-what your matcher is doing.
+what the matcher you have implemented is doing.
 The purpose of the $\textit{simp}$ function is to keep the regular
 expressions small. Normally the derivative function makes the regular
-expression bigger (see the SEQ case and the example in (2)) and the
+expression bigger (see the \texttt{SEQs} case and the example in Task (2)) and the
 algorithm would be slower and slower over time. The $\textit{simp}$
 function counters this increase in size and the result is that the
 algorithm is fast throughout.  By the way, this algorithm is by Janusz
 Brzozowski who came up with the idea of derivatives in 1964 in his PhD
 thesis.
 \url{https://en.wikipedia.org/wiki/Janusz_Brzozowski_(computer_scientist)}
 \end{center}
 If you want to see how badly the regular expression matchers do in
-Java\footnote{Version 8 and below; Version 9 and above does not seem to be as
+Java\footnote{Version 8 and below; Version 9 and above does not seem
-catastrophic, but still much worse than the regular expression
+to be as catastrophic, but still much worse than the regular
-matcher based on derivatives.}, JavaScript and Python with the
+expression matcher based on derivatives. BTW, Scala uses the regular
-``evil'' regular expression $(a^*)^*\cdot b$, then have a look at the
+expression matcher provided by the Java libraries. So is just as bad.}, JavaScript,
-graphs below (you can try it out for yourself: have a look at the files
+Python Swift and Dart with the ``evil'' regular expression
+$(a^*)^*\cdot b$, then have a look at the graphs below (you can try it
+out for yourself: have a look at the files
 \texttt{catastrophic9.java}, \texttt{catastrophic.js},
-\texttt{catastrophic.py} etc on KEATS). Compare this with the matcher you
+\texttt{catastrophic.py} etc on KEATS). Compare this with the matcher
-have implemented. How long can a string of $a$'s be in your matcher
+you have implemented. How long can a string of $a$'s be in your
-and still stay within the 30 seconds time limit? It should be muuuch better
+matcher and still stay within the 30 seconds time limit? It should be
-than your off-the-shelf matcher in your bog-standard language.
+mu(uu)$^*$ch better than your off-the-shelf matcher in your
+bog-standard language.
 \begin{center}
 \begin{tabular}{@{}cc@{}}
 \multicolumn{2}{c}{Graph: $(a^*)^*\cdot b$ and strings
 $\underbrace{a\ldots a}_{n}$}\medskip\\
 \end{document}
+For example given the regular expression $r = (a \cdot b) \cdot c$, the derivatives
+w.r.t.~the characters $a$, $b$ and $c$ are
+\begin{center}
+\begin{tabular}{lcll}
+$\textit{der}\;a\;r$ & $=$ & $(\ONE \cdot b)\cdot c$ & \quad($= r'$)\\
+$\textit{der}\;b\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$\\
+$\textit{der}\;c\;r$ & $=$ & $(\ZERO \cdot b)\cdot c$
+\end{tabular}
+\end{center}
+Let $r'$ stand for the first derivative, then taking the derivatives of $r'$
+w.r.t.~the characters $a$, $b$ and $c$ gives
+\begin{center}
+\begin{tabular}{lcll}
+$\textit{der}\;a\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$ \\
+$\textit{der}\;b\;r'$ & $=$ & $((\ZERO \cdot b) + \ONE)\cdot c$ & \quad($= r''$)\\
+$\textit{der}\;c\;r'$ & $=$ & $((\ZERO \cdot b) + \ZERO)\cdot c$
+\end{tabular}
+\end{center}
+One more example: Let $r''$ stand for the second derivative above,
+then taking the derivatives of $r''$ w.r.t.~the characters $a$, $b$
+and $c$ gives
+\begin{center}
+\begin{tabular}{lcll}
+$\textit{der}\;a\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$ \\
+$\textit{der}\;b\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ZERO$\\
+$\textit{der}\;c\;r''$ & $=$ & $((\ZERO \cdot b) + \ZERO) \cdot c + \ONE$ &
+(is $\textit{nullable}$)
+\end{tabular}
+\end{center}
+Note, the last derivative can match the empty string, that is it is \textit{nullable}.
 %%% Local Variables:
 %%% mode: latex
 %%% TeX-master: t
 %%% End:

changeset 428	cdfa6a293453
parent 426	b51467741af2
child 444	7a0735db4788