--- a/progs/re1.scala	Mon Feb 13 23:22:45 2017 +0000
+++ b/progs/re1.scala	Wed Mar 15 01:24:39 2017 +0000
@@ -1,3 +1,5 @@
+// Simple matcher for basic regular expressions
+
 
 abstract class Rexp
 case object ZERO extends Rexp                    // matches nothing
@@ -40,22 +42,27 @@
 // main matcher function
 def matches(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r))
 
+
 //examples from the homework
+
 val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b')))
 der('a', r)
 der('b', r)
 der('c', r)
 
-//optional (one or zero times)
+//optional regular expression (one or zero times)
 def OPT(r: Rexp) = ALT(r, ONE)
 
-//n-times (explicitly expanded)
+//n-times regular expression (explicitly expanded)
 def NTIMES(r: Rexp, n: Int) : Rexp = n match {
   case 0 => ONE
   case 1 => r
   case n => SEQ(r, NTIMES(r, n - 1))
 }
 
+
+// Test Cases
+
 // the evil regular expression  a?{n} a{n}
 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
 
@@ -88,3 +95,23 @@
   println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i))))
 }
 
+
+
+
+// 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)
+}
+
+// the expicit expansion in EVIL1(n) increases
+// drastically its size
+
+size(EVIL1(1))  // 5
+size(EVIL1(3))  // 17
+size(EVIL1(5))  // 29
+size(EVIL1(7))  // 41