579 

   581 \noindent

   580 

   582 For the calculation below, I prefer to use the more ``mathematical''

   581 

   583 notation for regular expressions. Therefore let us first look at this

   584 notation and the corresponding Scala code.

   585 

   586 \begin{center}

   587 \begin{tabular}{r@{\hspace{10mm}}l}

   588   ``mathematical'' notation &  \\

   589   for regular expressions & Scala code\smallskip\\

   590   $\ZERO$ &  \texttt{ZERO}\\

   591   $\ONE$  &  \texttt{ONE}\\

   592   $c$     &  \texttt{CHAR(c)}\\

   593   $\sum rs$ & \texttt{ALTs(rs)}\\  

   594   $\prod rs$ & \texttt{SEQs(rs)}\\  

   595   $r^*$ & \texttt{STAR(r)}

   596 \end{tabular}

   597 \end{center}

   598 

   599 \noindent

   600 My own convention is that \texttt{rs} stands for a list of regular

   601 expressions.  Also of note is that these are \textbf{all} regular

   602 expressions in Main 3 and the template file defines them as the

   603 (algebraic) datatype \texttt{Rexp}. A confusion might arise from the

   604 fact that there is also some shorthand notation for some regular

   605 expressions, namely

   606 

   607 \begin{lstlisting}[xleftmargin=10mm,numbers=none]

   608 def ALT(r1: Rexp, r2: Rexp) = ALTs(List(r1, r2))

   609 def SEQ(r1: Rexp, r2: Rexp) = SEQs(List(r1, r2))

   610 \end{lstlisting}

   611   

   612 \noindent

   613 Since these are functions, everything of the form \texttt{ALT(r1, r2)}

   614 will immediately be translated into the regular expression

   615 \texttt{ALTs(List(r1, r2))} (similarly for \texttt{SEQ}).  Maybe even

   616 more confusing is that Scala allows one to define

   617 \textit{extensions} that provide an even shorter notation for

   618 \texttt{ALT} and \texttt{SEQ}, namely

   619 

   620 \begin{center}

   621 \begin{tabular}{lclcl}

   622   \texttt{r1} $\sim$ \texttt{r2} & $\dn$ & \texttt{SEQ(r1, r2)} & $\dn$ & \texttt{SEQs(List(r1, r2))}\\

   623   \texttt{r1} $|$ \texttt{r2} & $\dn$ & \texttt{ALT(r1, r2)}    & $\dn$ & \texttt{ALTs(List(r1, r2))}\\

   624 \end{tabular}

   625 \end{center}

   626 

   627 \noindent

   628 The right hand sides are the fully expanded definitions.

   629 The reason for this even shorter notation is that in the mathematical

   630 notation one often writes 

   631 

   632 \begin{center}

   633 \begin{tabular}{lcl}

   634   $r_1 \;\cdot\; r_2$ & $\dn$ & $\prod\;[r_1, r_2]$\\

   635   $r_1 + r_2$ & $\dn$ & $\sum\;[r_1, r_2]$

   636 \end{tabular}

   637 \end{center}

   638 

   639 \noindent

   640 The first one is for binary \textit{sequence} regular expressions and

   641 the second for binary \textit{alternative} regular expressions.

   642 The regex in question in the shorthand notation is $(a + 1)\cdot a$,

   643 which is the same as

   644 

   645 \[

   646 \prod\; [\Sigma\,[a, 1], a]

   647 \]

   648 

   649 \noindent

   650 or in Scala code

   651 

   652 \[

   653 \texttt{(CHAR('a') | ONE)} \;\sim\; \texttt{CHAR('a')}

   654 \]  

   655 

   656 \noindent

   657 Using the mathematical notation, the definition of $\textit{der}$ is

   658 given by the rules:

   659 

   660 \begin{center}

   661 \begin{tabular}{llcl}

   662 (1) & $\textit{der}\;c\;(\ZERO)$ & $\dn$ & $\ZERO$\\

   663 (2) & $\textit{der}\;c\;(\ONE)$  & $\dn$ & $\ZERO$\\

   664 (3) & $\textit{der}\;c\;(d)$     & $\dn$ & $\textit{if}\; c = d\;\textit{then} \;\ONE \; \textit{else} \;\ZERO$\\

   665 (4) & $\textit{der}\;c\;(\sum\;[r_1,..,r_n])$ & $\dn$ & $\sum\;[\textit{der}\;c\;r_1,..,\textit{der}\;c\;r_n]$\\

   666 (5) & $\textit{der}\;c\;(\prod\;[])$ & $\dn$ & $\ZERO$\\  

   667 (6) & $\textit{der}\;c\;(\prod\;r\!::\!rs)$ & $\dn$ & $\textit{if}\;\textit{nullable}(r)$\\

   668    &   & & $\textit{then}\;(\prod\;(\textit{der}\;c\;r)\!::\!rs) + (\textit{der}\;c\;(\prod rs))$\\

   669    &   & & $\textit{else}\;(\prod\;(\textit{der}\;c\;r)\!::\! rs)$\\

   670 (7) & $\textit{der}\;c\;(r^*)$ & $\dn$ & $(\textit{der}\;c\;r)\cdot (r^*)$\\

   671 \end{tabular}

   672 \end{center}

   673 

   674 

   675 

   676 \noindent

   677 Let's finally do the calculation for the derivative of the regular

   678 expression with respect to the letter $a$ (in red is in each line which

   679 regular expression is ana-lysed):

   680 

   681 \begin{center}

   682 \begin{tabular}{cll}

   683       & $\textit{der}(a, \textcolor{red}{(a + 1) \cdot a})$ & by (6) and since $a + 1$ is nullable\\

   684 $\dn$ & $(\textit{der}(a, \textcolor{red}{a + 1})\cdot a) + \textit{der}(a, \,\prod\,[a])$  & by (4)\\

   685 $\dn$ & $((\textit{der}(a, \textcolor{red}{a}) + \texttt{der}(a, \ONE))\cdot a) + \textit{der}(a, \,\prod\,[a])$& by (3)\\

   686 $\dn$ & $((\ONE + \texttt{der}(a, \textcolor{red}{1}))\cdot a) + \textit{der}(a, \,\prod\,[a])$ & by (2)\\

   687 $\dn$ & $((\ONE + \ZERO)\cdot a) + \textit{der}(a, \textcolor{red}{\prod\,[a]})$ & by (6) and $a$ not being nullable\\

   688 $\dn$ & $((\ONE + \ZERO)\cdot a) + \prod\,[\texttt{der}(a, \textcolor{red}{a})]$ & by (3)\\

   689 $\dn$ & $((\ONE + \ZERO)\cdot a) + \prod\,[\ONE]$ \\  

   690 \end{tabular}  

   691 \end{center}

   692 

   693 \noindent

   694 Translating this result back into Scala code gives you

   695 

   696 \[

   697 \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{)}

   698 \]

   699 

   700