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