# HG changeset patch
# User Christian Urban <christian.urban@kcl.ac.uk>
# Date 1695651131 -3600
# Node ID 9541e073f2ed239c45f169971127996d415210a7
# Parent  2f3c077359c4e412f9fc150df85d9da2d4d48263
updated

diff -r 2f3c077359c4 -r 9541e073f2ed progs/matcher/re1.sc
--- a/progs/matcher/re1.sc	Mon Sep 25 13:14:34 2023 +0100
+++ b/progs/matcher/re1.sc	Mon Sep 25 15:12:11 2023 +0100
@@ -76,7 +76,7 @@
 // the optional regular expression (one or zero times)
 def OPT(r: Rexp) = ALT(r, ONE)   // r + 1
 
-// the n-times regular expression (explicitly expanded)
+// the n-times regular expression (explicitly expanded to SEQs)
 def NTIMES(r: Rexp, n: Int) : Rexp = n match {
   case 0 => ONE
   case 1 => r
diff -r 2f3c077359c4 -r 9541e073f2ed progs/matcher/re2.sc
--- a/progs/matcher/re2.sc	Mon Sep 25 13:14:34 2023 +0100
+++ b/progs/matcher/re2.sc	Mon Sep 25 15:12:11 2023 +0100
@@ -1,4 +1,4 @@
-// A Version of the matcher with an explicit 
+// A Version of the simple matcher with an explicit 
 // n-times regular expression
 //
 // this keeps the size of the regular expression in the
@@ -91,7 +91,7 @@
 def test2() = {
   println("Test (a*)* b")
 
-  for (i <- 0 to 22 by 2) {
+  for (i <- 0 to 20 by 2) {
     println(f"$i: ${time_needed(1, matcher(EVIL2, "a" * i))}%.5f")
   }
 }
@@ -108,8 +108,7 @@
 }
 
 // EVIL1(n) has now a constant size, no matter
-// what n is; also the derivative only grows 
-// moderately 
+// what n is
 
 size(EVIL1(1))  // 7
 size(EVIL1(3))  // 7
@@ -117,6 +116,9 @@
 size(EVIL1(7))  // 7
 size(EVIL1(20)) // 7
 
+// also the derivative only grows much more 
+// moderately and actually maxes out at size 211
+// (for n = 5)
 size(ders("".toList, EVIL1(5)))       // 7
 size(ders("a".toList, EVIL1(5)))      // 16
 size(ders("aa".toList, EVIL1(5)))     // 35
@@ -125,7 +127,9 @@
 size(ders("aaaaa".toList, EVIL1(5)))  // 122
 size(ders("aaaaaa".toList, EVIL1(5))) // 151
 
-size(ders(("a" * 20).toList, EVIL1(5))) 
+size(ders(("a" * 20).toList, EVIL1(5)))   // 211
+size(ders(("a" * 200).toList, EVIL1(5)))  // 211
+size(ders(("a" * 2000).toList, EVIL1(5))) // 211
 
 // but the size of the derivatives can still grow 
 // quite dramatically in case of EVIL2:  (a*)* b
diff -r 2f3c077359c4 -r 9541e073f2ed progs/matcher/re3.sc
--- a/progs/matcher/re3.sc	Mon Sep 25 13:14:34 2023 +0100
+++ b/progs/matcher/re3.sc	Mon Sep 25 15:12:11 2023 +0100
@@ -1,10 +1,10 @@
-// A version of the matcher with simplification 
+// A version of the simple matcher with simplification 
 // of derivatives
 //
-// this keeps the regular expressions small, which
+// this keeps the regular expressions (often) small, which
 // is good for the run-time
 // 
-// call the test cases with X = {1,2}
+// call the test cases with X = {1,2,3,4}
 //
 //   amm re3.sc testX
 //
@@ -23,7 +23,6 @@
 case class NTIMES(r: Rexp, n: Int) extends Rexp 
 
 
-
 // the nullable function: tests whether the regular 
 // expression can recognise the empty string
 def nullable (r: Rexp) : Boolean = r match {
@@ -67,7 +66,7 @@
   case r => r
 }
 
-// the derivative w.r.t. a string (iterates der)
+// the derivative w.r.t. a string (iterates der and simp)
 def ders(s: List[Char], r: Rexp) : Rexp = s match {
   case Nil => r
   case c::s => ders(s, simp(der(c, r)))
@@ -81,7 +80,7 @@
 // Test Cases
 //============
 
-// one or zero
+// optional is still just defined
 def OPT(r: Rexp) = ALT(r, ONE)
 
 // evil regular expressions: (a?){n} a{n}  and (a*)* b
@@ -130,7 +129,8 @@
 
 
 // now the size of the derivatives grows 
-// much, much slower
+// much, much slower and actually maxes out
+// at size 8
 
 size(ders("".toList, EVIL2))      // 5
 size(ders("a".toList, EVIL2))     // 8
@@ -139,6 +139,8 @@
 size(ders("aaaa".toList, EVIL2))  // 8
 size(ders("aaaaa".toList, EVIL2)) // 8
 
+size(ders(("a" * 20000).toList, EVIL2)) // 8
+
 
 @arg(doc = "All tests.")
 @main
diff -r 2f3c077359c4 -r 9541e073f2ed slides.sty
--- a/slides.sty	Mon Sep 25 13:14:34 2023 +0100
+++ b/slides.sty	Mon Sep 25 15:12:11 2023 +0100
@@ -113,6 +113,8 @@
 
 \setbeamercolor{boxcolor}{fg=black,bg=cream}
 
+
+
 \mode
 <all>
 
diff -r 2f3c077359c4 -r 9541e073f2ed slides/slides01.pdf
Binary file slides/slides01.pdf has changed
diff -r 2f3c077359c4 -r 9541e073f2ed slides/slides01.tex
--- a/slides/slides01.tex	Mon Sep 25 13:14:34 2023 +0100
+++ b/slides/slides01.tex	Mon Sep 25 15:12:11 2023 +0100
@@ -31,6 +31,7 @@
 %% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect2/main.pdf
 %% https://cs.rit.edu/~hh/teaching/_media/cc18/lectures/lect3/main.pdf
 
+
 \begin{document}
 
 %\begin{frame}[t]
@@ -310,10 +311,10 @@
   {\makebox[0mm]{\footnotesize
       \begin{tabular}{@{}r@{}}binary\\[-1mm]code\end{tabular}}};
 
-  \draw [->,line width=4mm] (0) -- (A); 
-  \draw [->,line width=4mm] (A) -- (B); 
-  \draw [->,line width=4mm] (B) -- (C); 
-  \draw [->,line width=4mm] (C) -- (1); 
+  \draw [->,line width=3mm] (0) -- (A); 
+  \draw [->,line width=3mm] (A) -- (B); 
+  \draw [->,line width=3mm] (B) -- (C); 
+  \draw [->,line width=3mm] (C) -- (1); 
   \end{tikzpicture}
   \end{center}
 
@@ -1708,15 +1709,15 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}\\[2cm]\alert{Questions?}\end{tabular}}
+\frametitle{\begin{tabular}{c}\\[1cm]\alert{Questions?}\end{tabular}}
 
 
 \begin{tabular}{lll}
   SGT TAs: & Flavio Melinte Citea & (was a KURF last summer)\\
            & Krishi Wali \\
            & Meilai Ji \medskip\\
-  Amm Helpers & Harry Dilnot & (harry.dilnot\@kcl.ac.uk)\\
-              & Meilai Ji & (meilai.ji\@kcl.ac.uk)\medskip\\
+  Amm Helpers & Harry Dilnot & (harry.dilnot@kcl.ac.uk)\\
+              & Meilai Ji & (meilai.ji@kcl.ac.uk)\medskip\\
 \end{tabular}  
 \mbox{}
 \end{frame}