--- a/progs/re2.scala	Mon Feb 13 23:22:45 2017 +0000
+++ b/progs/re2.scala	Wed Mar 15 01:24:39 2017 +0000
@@ -1,5 +1,6 @@
-// version with explicit an n-times regular expression
-// this keeps the regular expression small
+// Version with explicit an explicit n-times regular expression;
+// this keeps the overall regular expression in the EVIL1 regular 
+// expression small
 
 abstract class Rexp 
 case object ZERO extends Rexp
@@ -8,7 +9,8 @@
 case class ALT(r1: Rexp, r2: Rexp) extends Rexp 
 case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 
 case class STAR(r: Rexp) extends Rexp 
-case class NTIMES(r: Rexp, n: Int) extends Rexp //explicit constructor
+case class NTIMES(r: Rexp, n: Int) extends Rexp   //explicit constructor for n-times
+
 
 def nullable (r: Rexp) : Boolean = r match {
   case ZERO => false
@@ -20,6 +22,7 @@
   case NTIMES(r, i) => if (i == 0) true else nullable(r)
 }
 
+
 def der (c: Char, r: Rexp) : Rexp = r match {
   case ZERO => ZERO
   case ONE => ZERO
@@ -30,7 +33,7 @@
     else SEQ(der(c, r1), r2)
   case STAR(r1) => SEQ(der(c, r1), STAR(r1))
   case NTIMES(r1, i) => 
-    if (i == 0) ZERO else der(c, SEQ(r1, NTIMES(r1, i - 1)))
+    if (i == 0) ZERO else SEQ(der(c, r1), NTIMES(r1, i - 1))
 }
 
 def ders (s: List[Char], r: Rexp) : Rexp = s match {
@@ -41,9 +44,12 @@
 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r))
 
 
-//optional: one or zero times
+//optional regular expression: one or zero times
 def OPT(r: Rexp) = ALT(r, ONE)
 
+
+// Test Cases
+
 //evil regular expressions
 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
 val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
@@ -57,11 +63,11 @@
 
 
 //test: (a?{n}) (a{n})
-for (i <- 1 to 1001 by 10) {
+for (i <- 1 to 1201 by 100) {
   println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i))))
 }
 
-for (i <- 1 to 1001 by 10) {
+for (i <- 1 to 1201 by 100) {
   println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i))))
 }
 
@@ -76,3 +82,32 @@
 }
 
 
+
+// size of a regular expressions - for testing purposes 
+def size(r: Rexp) : Int = r match {
+  case ZERO => 1
+  case ONE => 1
+  case CHAR(_) => 1
+  case ALT(r1, r2) => 1 + size(r1) + size(r2)
+  case SEQ(r1, r2) => 1 + size(r1) + size(r2)
+  case STAR(r) => 1 + size(r)
+  case NTIMES(r, _) => 1 + size(r)
+}
+
+// EVIL1(n) has now a constant size, no matter
+// what n is 
+
+size(EVIL1(1))  // 7
+size(EVIL1(3))  // 7
+size(EVIL1(5))  // 7
+size(EVIL1(7))  // 7
+
+
+// but the size of the derivatives can grow 
+// quite dramatically
+
+size(ders("".toList, EVIL2))     // 5
+size(ders("a".toList, EVIL2))    // 12
+size(ders("aa".toList, EVIL2))   // 28
+size(ders("aaa".toList, EVIL2))  // 58
+size(ders("aaaa".toList, EVIL2)) // 116