--- 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