progs/matcher/re2.sc
changeset 929 9541e073f2ed
parent 919 53f08d873e09
--- 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