
diff -r 78cb5cdda3c3 -r a1151868a997 cws/main_cw03.tex
--- a/cws/main_cw03.tex	Mon Dec 25 01:10:55 2023 +0100
+++ b/cws/main_cw03.tex	Fri Feb 23 11:31:36 2024 +0000
@@ -574,11 +574,130 @@
 \end{tikzpicture}
 \end{tabular}  
 \end{center}
+
+%\end{document}
 \newpage
 
+\noindent
+For the calculation below, I prefer to use the more ``mathematical''
+notation for regular expressions. Therefore let us first look at this
+notation and the corresponding Scala code.
+
+\begin{center}
+\begin{tabular}{r@{\hspace{10mm}}l}
+  ``mathematical'' notation &  \\
+  for regular expressions & Scala code\smallskip\\
+  $\ZERO$ &  \texttt{ZERO}\\
+  $\ONE$  &  \texttt{ONE}\\
+  $c$     &  \texttt{CHAR(c)}\\
+  $\sum rs$ & \texttt{ALTs(rs)}\\  
+  $\prod rs$ & \texttt{SEQs(rs)}\\  
+  $r^*$ & \texttt{STAR(r)}
+\end{tabular}
+\end{center}
+
+\noindent
+My own convention is that \texttt{rs} stands for a list of regular
+expressions.  Also of note is that these are \textbf{all} regular
+expressions in Main 3 and the template file defines them as the
+(algebraic) datatype \texttt{Rexp}. A confusion might arise from the
+fact that there is also some shorthand notation for some regular
+expressions, namely
+
+\begin{lstlisting}[xleftmargin=10mm,numbers=none]
+def ALT(r1: Rexp, r2: Rexp) = ALTs(List(r1, r2))
+def SEQ(r1: Rexp, r2: Rexp) = SEQs(List(r1, r2))
+\end{lstlisting}
+  
+\noindent
+Since these are functions, everything of the form \texttt{ALT(r1, r2)}
+will immediately be translated into the regular expression
+\texttt{ALTs(List(r1, r2))} (similarly for \texttt{SEQ}).  Maybe even
+more confusing is that Scala allows one to define
+\textit{extensions} that provide an even shorter notation for
+\texttt{ALT} and \texttt{SEQ}, namely
+
+\begin{center}
+\begin{tabular}{lclcl}
+  \texttt{r1} $\sim$ \texttt{r2} & $\dn$ & \texttt{SEQ(r1, r2)} & $\dn$ & \texttt{SEQs(List(r1, r2))}\\
+  \texttt{r1} $|$ \texttt{r2} & $\dn$ & \texttt{ALT(r1, r2)}    & $\dn$ & \texttt{ALTs(List(r1, r2))}\\
+\end{tabular}
+\end{center}
+
+\noindent
+The right hand sides are the fully expanded definitions.
+The reason for this even shorter notation is that in the mathematical
+notation one often writes 
+
+\begin{center}
+\begin{tabular}{lcl}
+  $r_1 \;\cdot\; r_2$ & $\dn$ & $\prod\;[r_1, r_2]$\\
+  $r_1 + r_2$ & $\dn$ & $\sum\;[r_1, r_2]$
+\end{tabular}
+\end{center}
+
+\noindent
+The first one is for binary \textit{sequence} regular expressions and
+the second for binary \textit{alternative} regular expressions.
+The regex in question in the shorthand notation is $(a + 1)\cdot a$,
+which is the same as
+
+\[
+\prod\; [\Sigma\,[a, 1], a]
+\]
+
+\noindent
+or in Scala code
+
+\[
+\texttt{(CHAR('a') | ONE)} \;\sim\; \texttt{CHAR('a')}
+\]  
+
+\noindent
+Using the mathematical notation, the definition of $\textit{der}$ is
+given by the rules:
+
+\begin{center}
+\begin{tabular}{llcl}
+(1) & $\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\
+(2) & $\textit{der}\;c\;(\ONE)$  & $\dn$ & $\ZERO$\\
+(3) & $\textit{der}\;c\;(d)$     & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\
+(4) & $\textit{der}\;c\;(\sum\;[r_1,..,r_n])$ & $\dn$ & $\sum\;[\textit{der}\;c\;r_1,..,\textit{der}\;c\;r_n]$\\
+(5) & $\textit{der}\;c\;(\prod\;[])$ & $\dn$ & $\ZERO$\\  
+(6) & $\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)$\\
+(7) & $\textit{der}\;c\;(r^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\
+\end{tabular}
+\end{center}
+
 
 
+\noindent
+Let's finally do the calculation for the derivative of the regular
+expression with respect to the letter $a$ (in red is in each line which
+regular expression is ana-lysed):
 
+\begin{center}
+\begin{tabular}{cll}
+      & $\textit{der}(a, \textcolor{red}{(a + 1) \cdot a})$ & by (6) and since $a + 1$ is nullable\\
+$\dn$ & $(\textit{der}(a, \textcolor{red}{a + 1})\cdot a) + \textit{der}(a, \,\prod\,[a])$  & by (4)\\
+$\dn$ & $((\textit{der}(a, \textcolor{red}{a}) + \texttt{der}(a, \ONE))\cdot a) + \textit{der}(a, \,\prod\,[a])$& by (3)\\
+$\dn$ & $((\ONE + \texttt{der}(a, \textcolor{red}{1}))\cdot a) + \textit{der}(a, \,\prod\,[a])$ & by (2)\\
+$\dn$ & $((\ONE + \ZERO)\cdot a) + \textit{der}(a, \textcolor{red}{\prod\,[a]})$ & by (6) and $a$ not being nullable\\
+$\dn$ & $((\ONE + \ZERO)\cdot a) + \prod\,[\texttt{der}(a, \textcolor{red}{a})]$ & by (3)\\
+$\dn$ & $((\ONE + \ZERO)\cdot a) + \prod\,[\ONE]$ \\  
+\end{tabular}  
+\end{center}
+
+\noindent
+Translating this result back into Scala code gives you
+
+\[
+\texttt{ALT(\,} \underbrace{\texttt{(ONE | ZERO)} \sim \texttt{CHAR('a')}}_{(\textbf{1} + \textbf{0})\,\cdot\, a}\;,\;\underbrace{\texttt{SEQs(List(ONE))}}_{\prod\,[\textbf{1}]}\texttt{)}
+\]
+
+ 
 
 \end{document}
 




