equal
deleted
inserted
replaced
30 and Java (the plots on the left). For this consider some experimental |
30 and Java (the plots on the left). For this consider some experimental |
31 data: The first pair of plots shows the running time for the |
31 data: The first pair of plots shows the running time for the |
32 regular expression $(a^*)^*\cdot b$ and strings composed of $n$ |
32 regular expression $(a^*)^*\cdot b$ and strings composed of $n$ |
33 \pcode{a}s, like |
33 \pcode{a}s, like |
34 \[ |
34 \[ |
35 \pcode{"}\!\underbrace{\pcode{a}\ldots\pcode{a}}_{n}\!\pcode{"} |
35 \underbrace{\pcode{a}\ldots\pcode{a}}_{n} |
36 \] |
36 \] |
37 |
37 |
38 \noindent |
38 \noindent |
39 This means the regular expression actually does not match the strings. |
39 This means the regular expression actually does not match the strings. |
40 The second pair of plots shows the running time for the regular |
40 The second pair of plots shows the running time for the regular |
478 the time from the original string until the string is exhausted. |
478 the time from the original string until the string is exhausted. |
479 Having $\textit{der}s$ in place, we can finally define our matching |
479 Having $\textit{der}s$ in place, we can finally define our matching |
480 algorithm: |
480 algorithm: |
481 |
481 |
482 \[ |
482 \[ |
483 \textit{matches}\,r\,s \dn \textit{nullable}(\textit{ders}\,s\,r) |
483 \textit{matcher}\,r\,s \dn \textit{nullable}(\textit{ders}\,s\,r) |
484 \] |
484 \] |
485 |
485 |
486 \noindent |
486 \noindent |
487 and we can claim that |
487 and we can claim that |
488 |
488 |
489 \[ |
489 \[ |
490 \textit{matches}\,r\,s\quad\text{if and only if}\quad s\in L(r) |
490 \textit{matcher}\,r\,s\quad\text{if and only if}\quad s\in L(r) |
491 \] |
491 \] |
492 |
492 |
493 \noindent holds, which means our algorithm satisfies the |
493 \noindent holds, which means our algorithm satisfies the |
494 specification. Of course we can claim many things\ldots |
494 specification. Of course we can claim many things\ldots |
495 whether the claim holds any water is a different question, |
495 whether the claim holds any water is a different question, |
506 |
506 |
507 Another attraction of the algorithm is that it can be easily |
507 Another attraction of the algorithm is that it can be easily |
508 implemented in a functional programming language, like Scala. |
508 implemented in a functional programming language, like Scala. |
509 Given the implementation of regular expressions in Scala shown |
509 Given the implementation of regular expressions in Scala shown |
510 in the first lecture and handout, the functions and subfunctions |
510 in the first lecture and handout, the functions and subfunctions |
511 for \pcode{matches} are shown in Figure~\ref{scala1}. |
511 for \pcode{matcher} are shown in Figure~\ref{scala1}. |
512 |
512 |
513 \begin{figure}[p] |
513 \begin{figure}[p] |
514 \lstinputlisting[numbers=left,linebackgroundcolor= |
514 \lstinputlisting[numbers=left,linebackgroundcolor= |
515 {\ifodd\value{lstnumber}\color{capri!3}\fi}] |
515 {\ifodd\value{lstnumber}\color{capri!3}\fi}] |
516 {../progs/app5.scala} |
516 {../progs/app5.scala} |
1043 |
1043 |
1044 \[ |
1044 \[ |
1045 \textit{nullable}(\textit{ders}\,s\,r) |
1045 \textit{nullable}(\textit{ders}\,s\,r) |
1046 \] |
1046 \] |
1047 |
1047 |
1048 \noindent But this is just the definition of $matches$ |
1048 \noindent But this is just the definition of $matcher$ |
1049 |
1049 |
1050 \[ |
1050 \[ |
1051 matches\,s\,r \dn nullable(\textit{ders}\,s\,r) |
1051 matcher\,s\,r \dn nullable(\textit{ders}\,s\,r) |
1052 \] |
1052 \] |
1053 |
1053 |
1054 \noindent In effect we have shown |
1054 \noindent In effect we have shown |
1055 |
1055 |
1056 \[ |
1056 \[ |
1057 matches\,s\,r\;\;\text{if and only if}\;\; |
1057 matcher\,s\,r\;\;\text{if and only if}\;\; |
1058 s\in L(r) |
1058 s\in L(r) |
1059 \] |
1059 \] |
1060 |
1060 |
1061 \noindent which is the property we set out to prove: our algorithm |
1061 \noindent which is the property we set out to prove: our algorithm |
1062 meets its specification. To have done so, requires a few induction |
1062 meets its specification. To have done so, requires a few induction |