diff -r 1f4e81950ab4 -r 9476086849ad progs/re3a.scala
--- a/progs/re3a.scala	Mon Nov 14 15:50:42 2016 +0000
+++ b/progs/re3a.scala	Sat Jan 07 14:52:26 2017 +0000
@@ -74,7 +74,7 @@
 //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'))
-
+val EVIL3 = SEQ(STAR(ALT(CHAR('a'), SEQ(CHAR('a'),CHAR('a')))), CHAR('b'))
 
 def time_needed[T](i: Int, code: => T) = {
   val start = System.nanoTime()
@@ -94,11 +94,25 @@
 }
 
 //test: (a*)* b
-for (i <- 1 to 7000001 by 500000) {
+for (i <- 1 to 5000001 by 500000) {
+  println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i))))
+}
+
+for (i <- 1 to 5000001 by 500000) {
   println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i))))
 }
 
-for (i <- 1 to 7000001 by 500000) {
-  println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i))))
+
+val r0 = simp(der('a', EVIL3))
+val r1 = simp(der('a', r0))
+val r2 = simp(der('a', r1))
+val r3 = simp(der('a', r2))
+val r4 = simp(der('a', r3))
+val r5 = simp(der('a', r4))
+val r6 = simp(der('a', r5))
+
+//test: (a|aa)* b
+for (i <- 1 to 7001 by 500) {
+  println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL3, "a" * i ++ "c"))))
 }