22 match the strings).  To see the substantial differences in the left

    22 match the strings).  To see the substantial differences in the left

    23 and right plots below, note the different scales of the $x$-axes. 

    23 and right plots below, note the different scales of the $x$-axes. 

    24 

    24 

    25 

    25 

    26 \begin{center}

    26 \begin{center}

    27 \begin{tabular}{@{}cc@{}}

    28 \begin{tabular}{@{}cc@{}}

    28 \begin{tikzpicture}

    29 \begin{tikzpicture}

    29 \begin{axis}[

    30 \begin{axis}[

    31     ylabel={\small time in secs},

    33     ylabel={\small time in secs},

    32     enlargelimits=false,

    34     enlargelimits=false,

    33     xtick={0,5,...,30},

    35     xtick={0,5,...,30},

    34     xmax=33,

    36     xmax=33,

    35     ymax=35,

    37     ymax=35,

    48 \end{axis}

    50 \end{axis}

    49 \end{tikzpicture}

    51 \end{tikzpicture}

    50 &

    52 &

    51 \begin{tikzpicture}

    53 \begin{tikzpicture}

    52   \begin{axis}[

    54   \begin{axis}[

    54     ylabel={\small time in secs},

    57     ylabel={\small time in secs},

    55     enlargelimits=false,

    58     enlargelimits=false,

    56     xtick={0,3000,...,12000},

    59     xtick={0,3000,...,12000},

    57     xmax=12500,

    60     xmax=12500,

    58     ymax=35,

    61     ymax=35,

    67 \end{tikzpicture}

    70 \end{tikzpicture}

    68 \end{tabular}

    71 \end{tabular}

    69 \end{center}

    72 \end{center}

    70 

    73 

    71 \begin{center}

    74 \begin{center}

    72 \begin{tabular}{@{}cc@{}}

    76 \begin{tabular}{@{}cc@{}}

    73 \begin{tikzpicture}

    77 \begin{tikzpicture}

    74 \begin{axis}[

    78 \begin{axis}[

    76     ylabel={time in secs},

    81     ylabel={time in secs},

    77     enlargelimits=false,

    82     enlargelimits=false,

    78     xtick={0,5,...,30},

    83     xtick={0,5,...,30},

    79     xmax=33,

    84     xmax=33,

    80     ymax=35,

    85     ymax=35,

    90 \end{axis}

    95 \end{axis}

    91 \end{tikzpicture}

    96 \end{tikzpicture}

    92 &

    97 &

    93 \begin{tikzpicture}

    98 \begin{tikzpicture}

    94   \begin{axis}[

    99   \begin{axis}[

    96     ylabel={time in secs},

   102     ylabel={time in secs},

    97     enlargelimits=false,

   103     enlargelimits=false,

    98     xtick={0,3000,...,12000},

   104     xtick={0,3000,...,12000},

    99     xmax=12500,

   105     xmax=12500,

   100     ymax=35,

   106     ymax=35,

   127 we cannot use the function $L$ directly for this, because in general

   133 we cannot use the function $L$ directly for this, because in general

   128 the set of strings $L$ returns is infinite (recall what $L(a^*)$ is).

   134 the set of strings $L$ returns is infinite (recall what $L(a^*)$ is).

   129 In such cases there is no way we can implement an exhaustive test for

   135 In such cases there is no way we can implement an exhaustive test for

   130 whether a string is member of this set or not. In contrast our

   136 whether a string is member of this set or not. In contrast our

   131 matching algorithm will operate on the regular expression $r$ and

   137 matching algorithm will operate on the regular expression $r$ and

   133 the matching algorithm, however, let us have a closer look at what it

   139 the matching algorithm, however, let us have a closer look at what it

   134 means when two regular expressions are equivalent.

   140 means when two regular expressions are equivalent.

   135 

   141 

   136 \subsection*{Regular Expression Equivalences}

   142 \subsection*{Regular Expression Equivalences}

   137 

   143 

   291 expression look like that can match just $s$? The definition

   297 expression look like that can match just $s$? The definition

   292 of this function is as follows:

   298 of this function is as follows:

   293 

   299 

   294 \begin{center}

   300 \begin{center}

   295 \begin{tabular}{l@ {\hspace{2mm}}c@ {\hspace{2mm}}l}

   301 \begin{tabular}{l@ {\hspace{2mm}}c@ {\hspace{2mm}}l}

   304   \end{tabular}

   310   \end{tabular}

   305 \end{center}

   311 \end{center}

   306 

   312 

   307 \noindent The first two clauses can be rationalised as

   313 \noindent The first two clauses can be rationalised as

   309 expression so that given the ``input'' regular expression can

   315 expression so that given the ``input'' regular expression can

   310 match a string of the form $c\!::\!s$, we want a regular

   316 match a string of the form $c\!::\!s$, we want a regular

   311 expression for $s$. Since neither $\ZERO$ nor $\ONE$

   317 expression for $s$. Since neither $\ZERO$ nor $\ONE$

   312 can match a string of the form $c\!::\!s$, we return

   318 can match a string of the form $c\!::\!s$, we return

   313 $\ZERO$. In the third case we have to make a

   319 $\ZERO$. In the third case we have to make a

   318 return $\ZERO$ since no string of the $c\!::\!s$ can be

   324 return $\ZERO$ since no string of the $c\!::\!s$ can be

   319 matched. Next come the recursive cases, which are a bit more

   325 matched. Next come the recursive cases, which are a bit more

   320 involved. Fortunately, the $+$-case is still relatively

   326 involved. Fortunately, the $+$-case is still relatively

   321 straightforward: all strings of the form $c\!::\!s$ are either

   327 straightforward: all strings of the form $c\!::\!s$ are either

   322 matched by the regular expression $r_1$ or $r_2$. So we just

   328 matched by the regular expression $r_1$ or $r_2$. So we just

   324 expressions and compose the results again with $+$. Makes

   330 expressions and compose the results again with $+$. Makes

   325 sense? 

   331 sense? 

   326 

   332 

   327 The $\cdot$-case is more complicated: if $r_1\cdot r_2$

   333 The $\cdot$-case is more complicated: if $r_1\cdot r_2$

   328 matches a string of the form $c\!::\!s$, then the first part

   334 matches a string of the form $c\!::\!s$, then the first part

   329 must be matched by $r_1$. Consequently, it makes sense to

   335 must be matched by $r_1$. Consequently, it makes sense to

   331 $r_1$ and ``appending'' $r_2$. There is however one exception

   337 $r_1$ and ``appending'' $r_2$. There is however one exception

   332 to this simple rule: if $r_1$ can match the empty string, then

   338 to this simple rule: if $r_1$ can match the empty string, then

   333 all of $c\!::\!s$ is matched by $r_2$. So in case $r_1$ is

   339 all of $c\!::\!s$ is matched by $r_2$. So in case $r_1$ is

   334 nullable (that is can match the empty string) we have to allow

   340 nullable (that is can match the empty string) we have to allow

   336 expression that can match $s$. Therefore we have to add the

   342 expression that can match $s$. Therefore we have to add the

   338 is again simple: if $r^*$ matches a string of the form

   344 is again simple: if $r^*$ matches a string of the form

   339 $c\!::\!s$, then the first part must be ``matched'' by a

   345 $c\!::\!s$, then the first part must be ``matched'' by a

   345 on sets:

   352 on sets:

   346 

   353 

   347 \begin{equation}\label{Der}

   354 \begin{equation}\label{Der}

   349 \end{equation}

   356 \end{equation}

   350 

   357 

   351 \noindent This operation essentially transforms a set of

   358 \noindent This operation essentially transforms a set of

   352 strings $A$ by filtering out all strings that do not start

   359 strings $A$ by filtering out all strings that do not start

   353 with $c$ and then strips off the $c$ from all the remaining

   360 with $c$ and then strips off the $c$ from all the remaining

   354 strings. For example suppose $A = \{f\!oo, bar, f\!rak\}$ then

   361 strings. For example suppose $A = \{f\!oo, bar, f\!rak\}$ then

   355 

   362 

   359 \]

   366 \]

   360  

   367  

   361 \noindent

   368 \noindent

   363 starts with $a$. With this operation we can state the following

   370 starts with $a$. With this operation we can state the following

   368 \]

   375 \]

   369 

   376 

   370 \noindent

   377 \noindent

   372 namely take the set of strings that $r$ can match (that is $L(r)$),

   379 namely take the set of strings that $r$ can match (that is $L(r)$),

   373 filter out all strings not starting with $c$ and strip off the $c$

   380 filter out all strings not starting with $c$ and strip off the $c$

   374 from the remaining strings---this is exactly the language that

   381 from the remaining strings---this is exactly the language that

   376 

   383 

   377 If we want to find out whether the string $abc$ is matched by

   384 If we want to find out whether the string $abc$ is matched by

   379 as follows

   386 as follows

   380 

   387 

   381 \begin{center}

   388 \begin{center}

   382 \begin{tabular}{rll}

   389 \begin{tabular}{rll}

   383 Input: $r_1$, $abc$\medskip\\

   390 Input: $r_1$, $abc$\medskip\\

   387 Step 4: & the string is exhausted; test & ($\textit{nullable}(r_4)$)\\

   394 Step 4: & the string is exhausted; test & ($\textit{nullable}(r_4)$)\\

   388         & whether $r_4$ can recognise the\\

   395         & whether $r_4$ can recognise the\\

   389         & empty string\smallskip\\

   396         & empty string\smallskip\\

   390 Output: & result of this test $\Rightarrow \textit{true} \,\text{or}\, \textit{false}$\\        

   397 Output: & result of this test $\Rightarrow \textit{true} \,\text{or}\, \textit{false}$\\        

   391 \end{tabular}

   398 \end{tabular}

   392 \end{center}

   399 \end{center}

   393 

   400 

   395 this algorithm. We want to know whether $abc \in L(r_1)$. We

   402 this algorithm. We want to know whether $abc \in L(r_1)$. We

   397 builds the set where all the strings not starting with $a$ are

   404 builds the set where all the strings not starting with $a$ are

   398 filtered out. Of the remaining strings, the $a$ is stripped

   405 filtered out. Of the remaining strings, the $a$ is stripped

   399 off. So we should still have $bc$ in the set.

   406 off. So we should still have $bc$ in the set.

   400 Then we continue with filtering out all strings not

   407 Then we continue with filtering out all strings not

   401 starting with $b$ and stripping off the $b$ from the remaining

   408 starting with $b$ and stripping off the $b$ from the remaining

   403 Finally we filter out all strings not starting with $c$ and

   410 Finally we filter out all strings not starting with $c$ and

   404 strip off $c$ from the remaining string. This is

   411 strip off $c$ from the remaining string. This is

   407 must contain the empty string. If not, then $abc$ was not in the 

   414 must contain the empty string. If not, then $abc$ was not in the 

   408 language we started with.

   415 language we started with.

   409 

   416 

   413 characters to strings. This can be done using the following

   420 characters to strings. This can be done using the following

   415 a regular expression as output.

   422 a regular expression as output.

   416 

   423 

   417 \begin{center}

   424 \begin{center}

   418 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}

   425 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}

   419   $\textit{ders}\, []\, r$     & $\dn$ & $r$ & \\

   426   $\textit{ders}\, []\, r$     & $\dn$ & $r$ & \\

   421   \end{tabular}

   428   \end{tabular}

   422 \end{center}

   429 \end{center}

   423 

   430 

   425 the time from the original string until it is exhausted.

   432 the time from the original string until it is exhausted.

   427 algorithm:

   434 algorithm:

   428 

   435 

   429 \[

   436 \[

   431 \]

   438 \]

   432 

   439 

   433 \noindent

   440 \noindent

   434 and we can claim that

   441 and we can claim that

   435 

   442 

   436 \[

   443 \[

   438 \]

   445 \]

   439 

   446 

   440 \noindent holds, which means our algorithm satisfies the

   447 \noindent holds, which means our algorithm satisfies the

   441 specification. Of course we can claim many things\ldots

   448 specification. Of course we can claim many things\ldots

   442 whether the claim holds any water is a different question,

   449 whether the claim holds any water is a different question,

   443 which for example is the point of the Strand-2 Coursework.

   450 which for example is the point of the Strand-2 Coursework.

   444 

   451 

   446 main attractions are simplicity and being fast, as well as

   454 main attractions are simplicity and being fast, as well as

   447 being easily extendable for other regular expressions such as

   455 being easily extendable for other regular expressions such as

   448 $r^{\{n\}}$, $r^?$, $\sim{}r$ and so on (this is subject of

   456 $r^{\{n\}}$, $r^?$, $\sim{}r$ and so on (this is subject of

   450 

   458 

   451 \subsection*{The Matching Algorithm in Scala}

   459 \subsection*{The Matching Algorithm in Scala}

   452 

   460 

   453 Another attraction of the algorithm is that it can be easily

   461 Another attraction of the algorithm is that it can be easily

   454 implemented in a functional programming language, like Scala.

   462 implemented in a functional programming language, like Scala.

   463   implement in functional languages, because their built-in pattern 

   471   implement in functional languages, because their built-in pattern 

   464   matching and recursion allow us to mimic the mathematical

   472   matching and recursion allow us to mimic the mathematical

   465   definitions very closely.\label{scala1}}

   473   definitions very closely.\label{scala1}}

   466 \end{figure}

   474 \end{figure}

   467 

   475 

   469 regular expression $a^?{}^{\{n\}}a^{\{n\}}$, we need to implement

   514 regular expression $a^?{}^{\{n\}}a^{\{n\}}$, we need to implement

   470 the optional regular expression and the exactly $n$-times

   515 the optional regular expression and the exactly $n$-times

   471 regular expression. This can be done with the translations

   516 regular expression. This can be done with the translations

   472 

   517 

   473 \lstinputlisting[numbers=none]{../progs/app51.scala}

   518 \lstinputlisting[numbers=none]{../progs/app51.scala}

   474 

   519 

   476 slightly worse then the matcher in Ruby and Python.

   521 slightly worse then the matcher in Ruby and Python.

   477 Ooops\ldots

   522 Ooops\ldots

   478 

   523 

   479 \begin{center}

   524 \begin{center}

   480 \begin{tikzpicture}

   525 \begin{tikzpicture}

   483     ylabel={time in secs},

   530     ylabel={time in secs},

   484     enlargelimits=false,

   531     enlargelimits=false,

   485     xtick={0,5,...,30},

   532     xtick={0,5,...,30},

   486     xmax=30,

   533     xmax=30,

   487     ytick={0,5,...,30},

   534     ytick={0,5,...,30},

   530 \end{center}

   577 \end{center}

   531 

   578 

   532 \noindent With this fix we have a constant ``size'' regular

   579 \noindent With this fix we have a constant ``size'' regular

   533 expression for our running example no matter how large $n$ is.

   580 expression for our running example no matter how large $n$ is.

   534 This means we have to also add cases for \pcode{NTIMES} in the

   581 This means we have to also add cases for \pcode{NTIMES} in the

   536 effect?

   583 effect?

   537 

   584 

   538 \begin{center}

   585 \begin{center}

   539 \begin{tikzpicture}

   586 \begin{tikzpicture}

   540 \begin{axis}[

   587 \begin{axis}[

   542     ylabel={time in secs},

   591     ylabel={time in secs},

   543     enlargelimits=false,

   592     enlargelimits=false,

   544     xtick={0,100,...,1000},

   593     xtick={0,100,...,1000},

   546     ytick={0,5,...,30},

   595     ytick={0,5,...,30},

   547     scaled ticks=false,

   596     scaled ticks=false,

   548     axis lines=left,

   597     axis lines=left,

   550     height=5cm, 

   599     height=5cm, 

   551     legend entries={Python,Ruby,Scala V1,Scala V2},  

   600     legend entries={Python,Ruby,Scala V1,Scala V2},  

   552     legend pos=outer north east,

   601     legend pos=outer north east,

   555 \addplot[blue,mark=*, mark options={fill=white}] 

   603 \addplot[blue,mark=*, mark options={fill=white}] 

   556   table {re-python.data};

   604   table {re-python.data};

   557 \addplot[brown,mark=pentagon*, mark options={fill=white}] 

   605 \addplot[brown,mark=pentagon*, mark options={fill=white}] 

   558   table {re-ruby.data};  

   606   table {re-ruby.data};  

   559 \addplot[red,mark=triangle*,mark options={fill=white}] 

   607 \addplot[red,mark=triangle*,mark options={fill=white}] 

   564 \end{tikzpicture}

   612 \end{tikzpicture}

   565 \end{center}

   613 \end{center}

   566 

   614 

   567 \noindent Now we are talking business! The modified matcher 

   615 \noindent Now we are talking business! The modified matcher 

   568 can within 30 seconds handle regular expressions up to

   616 can within 30 seconds handle regular expressions up to

   574 

   622 

   575 The moral is that our algorithm is rather sensitive to the

   623 The moral is that our algorithm is rather sensitive to the

   576 size of regular expressions it needs to handle. This is of

   624 size of regular expressions it needs to handle. This is of

   578 need to traverse the whole regular expression. There seems,

   626 need to traverse the whole regular expression. There seems,

   579 however, one more issue for making the algorithm run faster.

   627 however, one more issue for making the algorithm run faster.

   580 The derivative function often produces ``useless''

   628 The derivative function often produces ``useless''

   581 $\ZERO$s and $\ONE$s. To see this, consider $r = ((a

   629 $\ZERO$s and $\ONE$s. To see this, consider $r = ((a

   582 \cdot b) + b)^*$ and the following two derivatives

   630 \cdot b) + b)^*$ and the following two derivatives

   583 

   631 

   584 \begin{center}

   632 \begin{center}

   585 \begin{tabular}{l}

   633 \begin{tabular}{l}

   589 \end{tabular}

   637 \end{tabular}

   590 \end{center}

   638 \end{center}

   591 

   639 

   592 \noindent 

   640 \noindent 

   593 If we simplify them according to the simple rules from the

   641 If we simplify them according to the simple rules from the

   594 beginning, we can replace the right-hand sides by the 

   642 beginning, we can replace the right-hand sides by the 

   595 smaller equivalent regular expressions

   643 smaller equivalent regular expressions

   596 

   644 

   597 \begin{center}

   645 \begin{center}

   598 \begin{tabular}{l}

   646 \begin{tabular}{l}

   602 \end{tabular}

   650 \end{tabular}

   603 \end{center}

   651 \end{center}

   604 

   652 

   605 \noindent I leave it to you to contemplate whether such a

   653 \noindent I leave it to you to contemplate whether such a

   606 simplification can have any impact on the correctness of our

   654 simplification can have any impact on the correctness of our

   626 Line~\ref{simpline}.\label{scala2}}

   674 Line~\ref{simpline}.\label{scala2}}

   627 \end{figure}

   675 \end{figure}

   628 

   676 

   629 \begin{center}

   677 \begin{center}

   630 \begin{tikzpicture}

   678 \begin{tikzpicture}

   632     enlargelimits=false,

   684     enlargelimits=false,

   633     xtick={0,2000,...,12000},

   685     xtick={0,2000,...,12000},

   635     ytick={0,5,...,30},

   687     ytick={0,5,...,30},

   636     scaled ticks=false,

   688     scaled ticks=false,

   637     axis lines=left,

   689     axis lines=left,

   638     width=9cm,

   690     width=9cm,

   639     height=5cm, 

   691     height=5cm, 

   642 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data};

   694 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data};

   643 \end{axis}

   695 \end{axis}

   644 \end{tikzpicture}

   696 \end{tikzpicture}

   645 \end{center}

   697 \end{center}

   646 

   698 

   648 

   725 

   649 \section*{Proofs}

   726 \section*{Proofs}

   650 

   727 

   651 You might not like doing proofs. But they serve a very

   728 You might not like doing proofs. But they serve a very

   652 important purpose in Computer Science: How can we be sure that

   729 important purpose in Computer Science: How can we be sure that

   784 

   861 

   785 \noindent

   862 \noindent

   786 Given this recipe, I let you show

   863 Given this recipe, I let you show

   787 

   864 

   788 \begin{equation}

   865 \begin{equation}

   790 \label{dersprop}

   867 \label{dersprop}

   791 \end{equation}

   868 \end{equation}

   792 

   869 

   798 \]

   875 \]

   799 

   876 

   800 \noindent In this proof you can assume the following property

   877 \noindent In this proof you can assume the following property

   802 assume

   879 assume

   803 

   880 

   804 \[

   881 \[

   806 \]

   883 \]

   807 

   884 

   808 \noindent holds (this would be of course a property that

   885 \noindent holds (this would be of course a property that

   809 needs to be proved in a side-lemma by induction on $r$).

   886 needs to be proved in a side-lemma by induction on $r$).

   810 

   887 

   819 \noindent That is the problem we want to solve. Thinking a 

   896 \noindent That is the problem we want to solve. Thinking a 

   820 little, you will see that this problem is equivalent to the 

   897 little, you will see that this problem is equivalent to the 

   821 following problem

   898 following problem

   822 

   899 

   823 \begin{equation}

   900 \begin{equation}

   825 \label{dersstep}

   902 \label{dersstep}

   826 \end{equation}

   903 \end{equation}

   827 

   904 

   828 \noindent But we have shown above in \eqref{dersprop}, that

   905 \noindent But we have shown above in \eqref{dersprop}, that

   830 \eqref{dersstep} is equivalent to 

   907 \eqref{dersstep} is equivalent to 

   831 

   908 

   832 \begin{equation}

   909 \begin{equation}

   834 \label{prefinalstep}

   911 \label{prefinalstep}

   835 \end{equation}

   912 \end{equation}

   836 

   913 

   837 \noindent We have also shown that testing whether the empty

   914 \noindent We have also shown that testing whether the empty

   838 string is in a language is equivalent to the $\textit{nullable}$

   915 string is in a language is equivalent to the $\textit{nullable}$

   839 function; see \eqref{nullableprop}. That means

   916 function; see \eqref{nullableprop}. That means

   840 \eqref{prefinalstep} is equivalent with

   917 \eqref{prefinalstep} is equivalent with

   841  

   918  

   842 \[

   919 \[

   844 \] 

   921 \] 

   845 

   922 

   846 \noindent But this is just the definition of $matches$

   923 \noindent But this is just the definition of $matches$

   847 

   924 

   848 \[

   925 \[

   850 \]

   927 \]

   851 

   928 

   852 \noindent In effect we have shown

   929 \noindent In effect we have shown

   853 

   930 

   854 \[

   931 \[